Quicksort
-
int teile(char* arr,int l,int r) { int j=l, i=r+1; char pivot=arr[l]; // Pivot-Element waehlen for(;;) { //1.while Schleife while(arr[++j] < pivot) ; // kann das zum Problem werden ?? while(arr[--i] > pivot) ; if (j >= i) break; Schedl::swap(arr[i], arr[j]); // 3 Datenbewegungen } Schedl::swap(arr[l],arr[i]); // Pivot an endgueltige Position return(i); }sagen wir mal folgende Wortfolge soll sortiert werden:
XSTERIA
ich frag mich grad ob die 1.while Schleife dann nicht unendlich läuft.
Pivot ist der ganze linke Buchstabe also X .und alle kommenden sind kleiner als X.
Endlosschleife ?
-
Wie man's sieht. Der gültige Bereich von arr wird ganz schnell verlassen und dort findet die Schleife dann entweder doch was größeres als X oder sammelt ein segmentation fault auf.
-
Also schon wieder ein Sentinel ala Sedgewick.
-
Was besagt denn die kleine o Notation.
Die große besagt eine Funktion ist höchstens von einer gegebenen Komplexität.
Die klein o Notation besagt doch exakt dasselbe.
eine Funktion f ist von der komplexität g wenn gilt:
limes f/g =0 na klar wenn g größer ist als f und der limes gegen
unendlich läuft geht es gegen 0.Seh kein Unterschied zwischen o und O Notation
Außerdem hab ich mal gehört es gibt auch eine Notation die aussagt wieviel
Aufwand es mindestens ist.
-
Das kleine o wird verwendet, um zu sagen, dass ein Ausdruck vernachlässigbar klein gegenüber dem angegebenen Ausdruck ist
Was soll das bedeuten ?
eine Funktion x im Vergleich zu x^2 wird natürlich sehr klein im Unendlichen.
Soll das zeigen dass die Funktion x nicht zu quadratisch gehört sondern
doch eher zu linear. ??
-
da ja beide O Notation eben klein / groß heissen müssen doch beide
was miteinander zutun haben
-
blurry333 schrieb:
Soll das zeigen dass die Funktion x nicht zu quadratisch gehört sondern
doch eher zu linear. ??f(x)=x ist ziemlich unquadratisch, ja.
-
-
naja man könnte schon zeigen dass x sehr viel kleiner als x^2 ist.
Nichts anderes drückt ja die klein o Notation aus.
lim geht nämlich gegen Null
Aber wozu man es braucht versteh ich momentan nicht so