LaufzeitanalyseSelectionSource < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 11:17 Do 16.12.2004 | | Autor: | John |
Hi,
Ich soll eine Laufzeitanalyse für einen in Borland Delphi programmierten Selection Source durchführen.
Hab aber keine Ahnung wie das gehen soll.
Der Code sieht so aus;
For i:=1 to n-1 Do
For j:=i+1 to n Do
Begin
If Feld[i]>Feld[j] then self.tausche(i,j);
end;
n ist eine Konstante dessen Größe egal ist.
i und j sind Zählvariablen, des Typs Integer;
Feld ist eine Array in dem n-viele Zahlen des Typs Integer gespeichert werden.
self.tausche ist eine Dreieckstausch Prozedur, die i und j im Feld vertauscht.
Dér Code funktioniert so.
Beim ersten durchlaufen wir i zu eins, gleichzeitig wird j zu 2.
dann wird in der If-Verzweigung die erste Zah im Feld mit der 2. verglichen, wenn die 1. dann größer als die 2 ist, werden diese dann vertauscht.
DAnn wird dieinnere Schleife wieder aufgerufen.
Die erste Zahl im FEld wird dann mit der 3. postition vergleichen und imemr so weiter.
Ich meine man muß sich erstmal aufzeichnen wie sortiert wird, dann irgendwie Zählen und dann einen Zusammenhang zwischen Durchläufen und n herstellen.
Weiß jemand wie das geht?
Ich ahb schon mal angefangen :
also ich nehm mal 4 unterschiedliche Zahlen
1. 5 4 3 2
dann wird die 1. mit der 2. verglichen, weil 5 größer als 4 ist, wird getauscht.
2. 4 5 3 2
Dann wird die 1.mit der 3. verglichen, da 4 größer 3 wirde getauscht.
3. 3 5 4 2
1. mit 4 vergleich., 3 >2 tausch.
4. 2 5 4 3
1. Druchlauf zuende, die erste Zahlist aufjeden fall die erste. i wird nun 2.
2 wird mit 3 verglichen
5. 2 4 5 3
2 mit 4 verg. 4>3 tausch.
6. 2 3 5 4
2. Druchgang zuende 1 und 2 sind schon in richiger Reihenfolge i wird nun zu 3
3 wird mit 4 verglichen
7. 2 3 4 5
fertig! Zuende Sortiert.
Aber wie kann ich das nun Auswerten, aslo es ist sowas mit Worstcase O(n irgendwas) gesucht!
DAnke im Vorraus.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:18 Do 16.12.2004 | | Autor: | Lizard |
Hallo, der relevante Teil für die Analyse ist ja sicher der Code. Du solltest dich fragen, wie oft jede Elementaroperation durchgeführt wird. Solche Operationen finden sich nur in der If-Abfrage: Mehrere direkte Zugriffe auf das Array, welche immer in O(1) möglich sein sollten; ferner ein Vergleich ("größer als") und die Abfrage selbst. Du solltest dich davon überzeugen, daß diese Zeile in O(1) abgearbeitet werden kann.
Gut, wie oft wird sie denn abgearbeitet? Die verschachtelten For-Schleifen sind hier das Problem. Der Lösungsansatz ist meiner Meinung nach, die äußere For-Schleife Schritt für Schritt durchzugehen und dabei immer aufzuschreiben, wieviel Durchläufe die innere Schleife jeweils macht. Zum Beispiel sind es im ersten Durchlauf genau (n-2) Durchläufe. Wieviel sind es im nächsten? Wieviel im letzten? Wenn du darauf kommen kannst, sollte die Laufzeit eigentlich kein Problem mehr darstellen.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:18 Do 16.12.2004 | | Autor: | John |
Erstmal danke, aber ich hab da überhaupt keinen Durchblick mehr!!!!
Ich hab heute noch mal meinen Informatik Leherer gefragt, aber er hatte da nicht wirklich Lust mir das zu erklären, naja, jetzt schreib ich Mittwoch ne Klausur.
Also er hat mir vollgenes an die Tafel geschrieben:
Also er hat mir das mit dem Bubble Sort erklärt, also:
For i:=1 to n Do
For j:=1 to n Do
Dann kommen Vergleichsbefehle, die aber wohl irrelevant sind.
So dann wurde etwas in Rekordtempo an die Tafel geschrieben, das ich völlig nicht verstanden ahbe.
n + (n-1) + ...... + n/2
1 + 2 +.........+(n/2 + 1)
n+1 n+1 n+1
Und dann kommt man natürlich, wie könnte es anders sein das raus:
(n+1) n/2 = 1/2n² + 1/2 = O (n²)
Ich hab nur verstanden. dass bei 1/2 n² + 1/2 nur n² interessant ist, da wenn n unendlich groß wird ist es egal ob es halbiert wird oder mit 0,5 addiert wird, aber wie kommt man auf diesen Term?????????
|
|
|
| |
|
Hallo!
> Erstmal danke, aber ich hab da überhaupt keinen Durchblick
> mehr!!!!
> Ich hab heute noch mal meinen Informatik Leherer gefragt,
> aber er hatte da nicht wirklich Lust mir das zu erklären,
> naja, jetzt schreib ich Mittwoch ne Klausur.
Mmh, so was macht ihr schon in der Schule? Hast du vielleicht Informatik-LK oder so? Wir haben das erste im vierten Semester gemacht...
> Also er hat mir vollgenes an die Tafel geschrieben:
> Also er hat mir das mit dem Bubble Sort erklärt, also:
>
> For i:=1 to n Do
> For j:=1 to n Do
> Dann kommen Vergleichsbefehle, die aber wohl
> irrelevant sind.
Bist du sicher, dass du das hier richtig abgeschrieben hast? Wir hatten das wohl irgendwie anders definiert. Jedenfalls würde ich das aus diesem Algorithmus eigentlich folgendermaßen lesen:
Du sollst ja im Prinzip herausfinden, wie viele "Schritte" benötigt werden. Dafür fängst du am besten bei der innersten Schleife an (also hier: j:= ...). Da das j von 1 bis n läuft, werden n Schritte benötigt. Für jedes [mm] j\in [/mm] {1,...,n} wird irgendwas gemacht, also wird n-mal etwas gemacht.
Nun betrachtest du die Schleife drum herum: i läuft ebenfalls von 1 bis n. Das heißt, es wird auch n-mal für i etwas gemacht.
Um die komplette Anzahl der Schritte zu wissen, musst du nun einfach beides multiplizieren, also [mm] n*n=n^2 [/mm] (das wäre meiner Meinung nach das Ergebnis zu diesem Algorithmus hier!). Warum du das multiplizieren musst, kannst du dir so vorstellen:
für i=1 machst du für j n-mal etwas, für i=2 ebenfalls, also hast du schon 2*n, für i=3 machst du auch wieder für das j n-mal etwas und so weiter, bis du bei i=n angekommen bist, du machst also bei jedem i für dein j n-mal etwas. Und da du n i's hast, machst du eben n-mal n etwas.
> So dann wurde etwas in Rekordtempo an die Tafel
> geschrieben, das ich völlig nicht verstanden ahbe.
>
> n + (n-1) + ...... + n/2
> 1 + 2 +.........+(n/2 + 1)
>
> n+1 n+1 n+1
Hier weiß ich im Moment auch nicht, wie dein Lehrer da drauf gekommen ist... ![[haee]](/images/smileys/haee.gif "[haee]") Aber könnte es sein, dass die beiden Endterme "vertauscht" werden müssen? Es sieht mir hier danach aus, dass summiert wird von n bis [mm] \bruch{n}{2}+1 [/mm] und dann noch mal von [mm] \bruch{n}{2} [/mm] bis 1... Das wäre dann in Summenschreibweise: [mm] \summe_{i=1}^{n} [/mm] i aufgeteilt in [mm] \summe_{i=1}^{\bruch{n}{2}} [/mm] i und [mm] \summe_{i=\bruch{n}{2}+1}^{n} [/mm] i
warum das so aufgeteilt ist, ergibt sich wahrscheinlich daraus, wie man überhaupt auf diese Formel kommt, was ich dir im Moment leider nicht sagen kann...
Aber wie man auf die folgende Formel kommt, kann ich dir sagen:
> Und dann kommt man natürlich, wie könnte es anders sein das
> raus:
>
>
> (n+1) n/2 = 1/2n² + 1/2 = O (n²)
Das ist die Summenformel von Gauß. (Hier eine kleine Anekdote dazu:
Als Gauß in der ersten Klasse (vielleicht auch schon in der zweiten oder dritten, aber er war noch sehr jung für so was) war, gab ein Lehrer den Schülern die Aufgabe, alle Zahlen von 1 bis 100 zu addieren. Denn er hatte keine Lust, richtig Unterricht zu machen und dachte, bis die Kinder damit fertig sind, dauert es lange.
Aber Gauß hat das einfach so gemacht:
er hat die Zahlen "sortiert", nämlich die 1 mit der 100 zusammen getan, dann die 2 mit der 99 usw.. So erhielt er immer eine Summe von 101. Und insgesamt hat er so 50 Summen erhalten, also für n=100 (er sollte ja alle 100 Zahlen addieren) [mm] \bruch{n}{2}. [/mm] Also brauchte er nur noch zu rechnen:
50*101 und hatte das Ergebnis. Und nichts anderes besasgt seine Formel:
[mm] \summe_{i=1}^{n} [/mm] i = [mm] \bruch{n}{2}(n+1)
[/mm]
also genau das, was dein Lehrer auch raus hatte...
Falls du die Formel verstehen möchtest, kannst du's ja mal mit den Zahlen von 1 bis 10 genauso machen. Da kannst du ja auch leicht alle Zahlen so addieren um dein Ergebnis zu überprüfen.
> Ich hab nur verstanden. dass bei 1/2 n² + 1/2 nur n²
> interessant ist, da wenn n unendlich groß wird ist es egal
> ob es halbiert wird oder mit 0,5 addiert wird, aber wie
> kommt man auf diesen Term?????????
![[ok]](/images/smileys/ok.gif "[ok]")
Den Rest kann ich dir leider nicht beantworten. Aber wenn du das Prinzip immer noch überhaupt nicht verstanden hast, kannst du ja vielleicht nochmal einen anderen einfachen Algo angeben, den ihr hattet, dann versuche ich es daran mal zu erklären. 
Viele Grüße
Bastian
![[banane]](/images/smileys/banane.gif "[banane]")
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:50 Fr 17.12.2004 | | Autor: | John |
Erst mal danke, so ein bisschen ahb ich das schon verstanden, und das das was mit Gauß zu tun hat stimmt wohl auch.
Also ein anderer Algoritmus ist der Selection Sort:
For i:= 1 to n-1 Do
For j:=i+1 to n Do
irgendwelche Vergleiche.
also erstmal innere Schleife
j [mm] \in [/mm] {2,...,n}
also wird n-1 mal etwas gemacht.
äußere Schleife:
i [mm] \in [/mm] {1, ...n-1}
Also multiplizieren:
(n-1)*(n-1) = (n-1)²= n² -2n+ 1 O(n²) weil es im Endeffekt egal ist , wenn n unendlich groß ist, ob 2n abgezogen und 1 addiert wird.
Stimmt das??
Danke im Voraus
p.s hab Info Grundkurs
|
|
|
| |
|
Hallo nochmal!
Leider stimmt deine Lösung nicht, aber vielleicht ist es ein gutes Beispiel, um es dir zu erklären.
> Also ein anderer Algoritmus ist der Selection Sort:
>
> For i:= 1 to n-1 Do
> For j:=i+1 to n Do
> irgendwelche Vergleiche.
>
> also erstmal innere Schleife
>
> j [mm]\in[/mm] {2,...,n}
>
> also wird n-1 mal etwas gemacht.
Das stimmt nicht! Denn: dein [mm] j\notin\{2,...,n\}, [/mm] sondern [mm] j\in\{i+1,...,n\}. [/mm] Das heißt, das j hängt vom i ab! Das ist wichtig!
Wenn du nun also mal für i 1 einsetzt, ist [mm] j\in\{2,...,n\}, [/mm] für i=2 aber ist [mm] j\in\{3,...,n\} [/mm] usw.. Ist das klar?
Das heißt, für i=1 passiert mit dem j (n-1)-mal was. Für i=2 (n-2)-mal usw. bis du bei i=(n-1) angekommen bist, hier ist dann [mm] j\in \{i+1,...,n\}=\{(n-1)+1,...,n\}=\{n,...,n\}=\{n\} [/mm] (für dieses j passiert also nur einmal was...)
Du musst also folgendes rechnen:
(n-1)+(n-2)+(n-3)+...+(n-(n-1))+(n-(n-0))=n-1+n-2+n-3+...-...+n-n+1
so, um das zusammenzufassen, guckst du dir am besten nochmal den ersten Teil hier an: (also das links neben dem Gleichheitszeichen)
Wie viele Summanden stehen hier? (also wie viele Klammern?) Es sind (n-2). Siehst du, warum? Man kann sie leider nicht alle aufschreiben, weil man ja kein n gegeben hat. Aber du kannst es ja für beliebige n (z. B. 5) mal ausprobieren. Oder du guckst dir an: die "Zahlen" (also nicht die n's, die sind ja in jeder Klammer gleich) laufen von 1 bis (n-1), also haben wir (n-2) davon. Also sind das auch (n-2) Klammern.
Da man in diesem Fall die ganzen Klammern einfach weglassen kann (so, wie hinter dem Gleichheitszeichen), kann man die einzelnen Teile auch anders anordnen. Man erhält dann:
n+n+...+n-1-2-3-...-(n-1)
Die Frage ist nun nur noch, wie viele n's hier addiert werden, denn wie viele Zahlen subtrahiert werden, haben wir ja gerade schon herausgefunden: von 1 bis (n-1), also (n-2). Das würde man dann als Summe so schreiben:
[mm] \summe_{i=1}^{n-1}i=\bruch{1}{2}(n-1)((n-1)+1)=\bruch{1}{2}(n-1)n=\bruch{1}{2}n^2-\bruch{1}{2}n
[/mm]
So, nun zu den n's: wir hatten ja in jeder Klammer, in der eine "Zahl" stand, auch ein n, also haben wir auch genauso viele n's wie Klammern, und das waren ja (n-2) Stück. Also wird das n (n-2)-mal addiert, wir erhalten also n*(n-2)
Und zusammengefasst ergibt das nun:
(beachte, dass hier nur das zu dem Summenzeichen gehört, was direkt dahinter steht, nicht das, was hinter dem nächsten "+" steht, sonst müssten Klammern gesetzt sein)
[mm] \summe_{i=1}^{n-1}i [/mm] + n*(n-2) = [mm] \summe_{i=1}^{n-1}i+n^2-2n [/mm] = [mm] \bruch{1}{2}n^2-\bruch{1}{2}n+n^2-2n [/mm] = [mm] n^2(\bruch{1}{2}+1)-n(\bruch{1}{2}+2)
[/mm]
Die letzte Umformung ist nicht unbedingt nötig, denn man sieht auch vorher schon, dass man es hier mit [mm] O(n^2) [/mm] zu tun hat. Du kannst es aber nach dem letzten Schritt noch so begründen:
wenn n immer größer wird, wird auch [mm] n^2 [/mm] immer größer, und es wird wesentlich schneller größer als das n, das ja von dem Ganzen wieder abgezogen wird. Ob du nun noch Faktoren davor stehen hast, ist natürlich wieder egal, wie beim letzten Mal auch.
> äußere Schleife:
>
> i [mm]\in[/mm] {1, ...n-1}
>
> Also multiplizieren:
> (n-1)*(n-1) = (n-1)²= n² -2n+ 1 O(n²)
> weil es im Endeffekt egal ist , wenn n unendlich groß ist,
> ob 2n abgezogen und 1 addiert wird.
>
>
> Stimmt das??
>
> Danke im Voraus
> p.s hab Info Grundkurs
So, ich habe es jetzt sehr ausführlich erklärt. Wenn du hiervon etwas nicht verstehst, dann zitiere in deiner nächsten Frage einfach meinen Text und schreiben deine Frage direkt an die entsprechende Stelle, die du nicht verstehst. Ich kann nämlich nicht alles nochmal erklären, ich würde es nur genauso machen und du würdest es wieder nicht verstehen. Aber wenn du einzelne Fragen zu einzelnen Schritten hier hast, dann helfe ich dir gerne weiter.
Viele Grüße
Bastiane
|
|
|
| |
|
Hallo.
Da ich gleich zur Info-Vorlesung muss und eine Frage reserviert ist, antworte ich einfach hier (man mag es mit bitte verzeihen)
Es gibt in diesem Fall zwei Möglichkeiten.
1. Man erkennt, dass es sich um Bubble-Sort handelt und weiß (Fachliches Allgemeinwissen), dass es sich um die Aufwandsklasse [mm] O(n^{2}) [/mm] handelt oder
2. Man zählt! die Anzahl der durchläufe. Die Aufwandsklasse ist eine obere Schranke für die Anzahl der durchgeführten Operationen. Es gelt ein paar einfache Regen und Fakten für Aufwandabschätzungen:
(i) Es werden die Vertauschungen berücksichtigt (weil: ist ein Sortieralgorithmus).
(ii) Es wird der Worst-Case betrachtet.
(iii) Es darf nach oben abgeschätzt werden (da obere Schranke)
Mit diesen Überlegungen/Fakten kann man die Schleifen analysieren:
(a) Die außere Schleife wird von 1 bis (n-1) durchgeführt. (Also n-mal nach oben abgeschätzt, aber das brauchen wir nicht)
(b) Die innere Schleife wird im ersten Schritt n-mal, dann (n-1)-mal, dann (n-2)-mal usw. bis 1-mal durchgeführt (wegen (a)). Das wird dann addiert:
1+2+3+...+(n-1) = (nach Gauss;) [mm] \bruch{(n-1)+1}{2}*n [/mm] = [mm] \bruch{n}{2}*n [/mm] = [mm] \bruch{1}{2} n^{2} \hat= [/mm] (nach (iii)) [mm] n^{2}
[/mm]
(c) Es werden die Vertauschungen berücksichtigt. Da es in der inneren Schleife genau eine gibt ist es gleich zu der Anzahl der Durchläufe (nach (ii))
[mm] \Rightarrow [/mm] Also ergibt sich als obere Schranke [mm] O(n^{2}). [/mm] Also anders ausgedrückt: Der Algorithmus wird -unabhängig von der Anordnung des Feldes- nie mehr [mm] n^{2} [/mm] Vertauschungen vornehmen.
Hat es geholfen? Ich bin jetzt bei meiner Übung (Info I)
Tschööö, Thomas :)
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:25 Fr 17.12.2004 | | Autor: | John |
ERstmal danke, wie beurteilst du denn meine Lösung zum Selection Source, ist ide Richtig?
wenn nicht kann mir jemand kurz dieses Gausse Verfahren erklären
|
|
|
| |
|
Hallo.
Was meinst du mit "Selection Source". Der Algorithmus, den du benutzt wird im Allgemeinen "Bubble-Sort" genannt. Das liegt daran, dass die kleinsten/größten Werte an den Anfang/das Ende wie blasen in einem Glas Wasser aufsteigen. Mehr dazu findest du unter ![[]](/images/popup.gif) Wikipedia (<- ist immer ein guter Tip!).
Das mit dem Gauss hat Bastiane oben schon erzählt. Mathematisch passiert nix tolles. Du hast ein Interval I=[1, n] mit n [mm] \in \IN [/mm] oder eine Menge M mit M = [mm] \{x | x \in \IN, n \ge x > 0, n \in \IN \backslash \{0\} beliebig \} \to [/mm] Zahlen von 1 bis n  .
Diese sollen alle Addiert werden.
(1) Die Addition ist kommutativ [mm] \to [/mm] du kannst dir aussuchen, in welcher Reihenfolge du addierst.
Das machen wir nun:
(2) Schreib alle Zahlen von 1 bis n der Reihe nach auf
(3) Nimm die erste und die letzte Zahl, addier die Beiden und schreib sie darunter in eine neue Zeile. Streich die beiden Zahlen durch
(4) Gehe zu 3, bis nur noch eine oder keine Zahl übrig ist
[Und mach das wirklich mal (1-12 oder so)! Dann wird einiges klarer]
Addier die Zahlen der Zeile darunter.
(5)Du wirst sehen, es sind immer die gleichen Zahlen (nämlich a = n+1)
(6) Wenn dein n gerade ist, bleibt keine Zahl übrig, also hast du (n/2)-mal die Zahl a
Summe = [mm] \bruch{n}{2}*(n+1) [/mm] = [mm] \bruch{n*(n+1)}{2} [/mm] = [mm] \bruch{n^{2}+n}{2}
[/mm]
(7) Wenn dein n ungerade ist, bleibt eine Zahl übrig [mm] (\bruch{n+1}{2}), [/mm] und du hast [mm] \bruch{n-1}{2} [/mm] die Zahl a
Summe = [mm] \bruch{n-1}{2}*(n+1) [/mm] + [mm] \bruch{n+1}{2} [/mm] = [mm] \bruch{(n-1)*(n+1)}{2} [/mm] + [mm] \bruch{n+1}{2} [/mm] = (3. bin. Formel) [mm] \bruch{n^{2}-1}{2} [/mm] + [mm] \bruch{n+1}{2} [/mm] = [mm] \bruch{n^{2}-1+n+1}{2} [/mm] = [mm] \bruch{n^{2}+n}{2}
[/mm]
Und somit kann man (relativ leicht) die Formel verifizieren:
(8) 1+2+...+n = [mm] \bruch{n^{2}+n}{2}
[/mm]
Die Antwort ist wie guter Wein...erst nach langer Zeit richtig gut (oder Weinessig)
Thomas :)
|
|
|
|
