O-Notation < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Hallo,
a) Laufzeit z.b. Selection Sort
b) Laufzeit ausgedachter Suchalgorithmus aus unserem Buch
also ich hab bisschen Probleme mit der Laufzeit-bestimmung in Schleifen. |
Also ich hab mal drei Funktionen gepostet (in C geschrieben),
von denen ich die Laufzeit bestimmen soll.
a)
void insertion_sort(int *A,int l,int r){
int i,j,z;
for(i=l+1;i<=r;i++){
z=A[i];
for(j=i-1;j>=l;j--){
if(z<A[j]) A[j+1]=A[j];
else
break;
}
A[j+1]=z;
}
}
die erste Schleife benötigt n-1 Iterationen. Soweit klar.
Die zweite benötigt je nachdem nur eine,2,3, oder halt n-1 Iterationen, weil
schon nach einer Abfrage die Schleife abgebrochen werden kann aber auch erst nach n-1
Ist eigentlich auch klar.
Aber wie kommt man jetzt auf O(n²)??
Wir addieren das im Buch:
(1+2+...+N-2+N-1)*O(1)+O(1)+O(N-1)*O(1)
Wieso wird hier addiert? in verschachtelten Schleifen dachte ich immer eher, dass multipliziert wird?
zweites Beispiel:
void sortieren(int anzahl,int array[])
{
int i,t;
for(i=1;i<anzahl;i++)
{
if(array[i-1]<array[i])
{
t=array[i];
array[i] = array[i-1];
array[i-1] = t;
i=0;
}
}
}
Laut Lösung ergibt sich hier eine Laufzeit von O(n³)?
Ich hätte eher O(n²) gesagt.
1. Eine for-Schleife, die n-mal läuft und in jeder positiven if-Abfrage wird i auf null zurückgesetzt also
1,2,3,...,n-1,n mal Durchläufe max.
Also O(n²) oder?
Wäre super, wenn mir das jemand erklären könnte, weil das Thema beschäftigt mich einfach; und ich komme einfach da nicht weiter.
Danke schonmal 
|
|
| |
|
Hallo!
> Hallo,
>
> a) Laufzeit z.b. Selection Sort
> b) Laufzeit ausgedachter Suchalgorithmus aus unserem Buch
>
>
> also ich hab bisschen Probleme mit der Laufzeit-bestimmung
> in Schleifen.
> Also ich hab mal drei Funktionen gepostet (in C
> geschrieben),
> von denen ich die Laufzeit bestimmen soll.
>
>
> a)
>
> void insertion_sort(int *A,int l,int r){
> int i,j,z;
> for(i=l+1;i<=r;i++){
> z=A;
> for(j=i-1;j>=l;j--){
>
> if(z<A[j]) A[j+1]=A[j];
> else
> break;
> }
> A[j+1]=z;
> }
> }
> [i][/i][/blue]
> die erste Schleife benötigt n-1 Iterationen. Soweit
> klar.
> Die zweite benötigt je nachdem nur eine,2,3, oder halt
> n-1 Iterationen, weil
> schon nach einer Abfrage die Schleife abgebrochen werden
> kann aber auch erst nach n-1
>
> Ist eigentlich auch klar.
> Aber wie kommt man jetzt auf O(n²)??
>
> Wir addieren das im Buch:
> (1+2+...+N-2+N-1)*O(1)+O(1)+O(N-1)*O(1)
>
> Wieso wird hier addiert? in verschachtelten Schleifen
> dachte ich immer eher, dass multipliziert wird?
Im Grunde wird nie "multipliziert", das solltest du dir nur ganz grob so merken: Wenn zwei Schleifen ineinandergeschachtelt sind, und beide Schleifendurchläufe haben etwa n Iterationen, dann kommt [mm] n^{2} [/mm] raus.
Exakt muss es aber eigentlich so sein:
Eine Schleife wirkt wie ein Summenzeichen [mm] \sum [/mm] für die Laufzeiten, die "in ihr" stattfinden. Leichtes Beispiel: Die Laufzeit von
for(i = 1; i <= n; i++) {
for (j = 1; j <= n; j++) {
cout << "Hallo" << endl;
}
}
würde man so ausrechnen:
Wir haben erst eine Schleife:
[mm] \sum_{i=1}^{n}\mbox{(Laufzeit des Inneren der ersten Schleife)}
[/mm]
Und dann noch eine Schleife darin:
= [mm] \sum_{i=1}^{n}\sum_{j=1}^{n}\mbox{Laufzeit des Inneren der zweiten Schleife}
[/mm]
Und die Laufzeit des Inneren der zweiten Schleife ist gerade konstant "1":
= [mm] \sum_{i=1}^{n}\sum_{j=1}^{n}1
[/mm]
Da die Laufzeit unabhängig von i und j ist, können wir nun einfach ausrechnen:
= [mm] \sum_{i=1}^{n}\sum_{j=1}^{n}1 [/mm] = [mm] \sum_{i=1}^{n}n [/mm] = n*n = [mm] n^{2}
[/mm]
Deswegen finden bei dieser Schleife [mm] n^{2} [/mm] Operationen statt, bzw. die Laufzeit ist [mm] n^{2}.
[/mm]
Okay?
Bei deinem Beispiel ist es nun nicht ganz so. Die innere Schleife hängt nämlich von der Laufvariable der äußeren ab. Im worst case sieht deine Schleife so aus:
for(i = 1; i <= n; i++) {
for (j = 1; j <= i; j++) {
cout << "Hallo" << endl;
}
}
Nun wieder die Laufzeit:
[mm] \sum_{i=1}^{n}\mbox{Laufzeit des Inneren der ersten Schleife}
[/mm]
= [mm] \sum_{i=1}^{n}\sum_{j=1}^{i}\mbox{Laufzeit des Inneren der zweiten Schleife}
[/mm]
= [mm] \sum_{i=1}^{n}\sum_{j=1}^{i}1
[/mm]
Nun muss so weitergerechnet werden:
= [mm] \sum_{i=1}^{n}i
[/mm]
Und nun gibt es für diese Summe eine (bekannte!) Summenformel:
= [mm] \frac{n*(n+1)}{2}\in O(n^{2}).
[/mm]
> zweites Beispiel:
>
> void sortieren(int anzahl,int array[])
> {
> int i,t;
>
> for(i=1;i<anzahl;i++)
> {
> if(array[i-1]<array)
> {
> t=array;
> array = array[i-1];
> array[i-1] = t;
> i=0;
> }
> }
> }
> [i][i][i][i] [/i][/i][/i][/i][/blue]
>
> Laut Lösung ergibt sich hier eine Laufzeit von O(n³)?
> Ich hätte eher O(n²) gesagt.
> 1. Eine for-Schleife, die n-mal läuft und in jeder
> positiven if-Abfrage wird i auf null zurückgesetzt also
> 1,2,3,...,n-1,n mal Durchläufe max.
> Also O(n²) oder?
Die Laufzeit ist tatsächlich [mm] O(n^{3}).
[/mm]
Du hast nicht ganz aufgepasst, wie der Algorithmus vorgeht. Es ist eine Art Bubblesort, aber es wird zusätzlich nach jedem Vertauschen (!) wieder von vorn angefangen.
Stellen wir uns den worst case vor:
Array
1,2,3,4,5,6
Dann vertauscht der Algorithmus zunächst 1 und 2, fängt dann aber wieder von vorne an.
2,1,3,4,5,6
Er überprüft wieder 2 und 1, und danach 1 und 3. Wieder vertauschen:
2,3,1,4,5,6
Nun fängt er wieder von vorne an und vertauscht 2 und 3:
3,2,1,4,5,6
Usw.
Wie lange braucht der Algorithmus also, um die Zahl "a" nach vorne zu holen, wenn die Zahl "a-1" schon ganz vorne ist?
Am Beispiel der 4 nochmal:
3,2,1,4,5,6
(a-1) Schritte bis zur 4, dann vertauschen mit der 1:
3,2,4,1,5,6
(a-2) Schritt bis zur 4, dann vertauschen mit der 2:
3,4,2,1,5,6
(a-3) Schritte bis zur 4, dann vertauschen mit der 3:
4,3,2,1,5,6.
Um also die Zahl "a" nach vorne zu bekommen, wenn die Zahl "a-1" bereits vorne ist, brauchen wir
$1+2+3+...+(a-1) = a*(a-1)/2$
Schritte!
Ich will ja aber am Ende auch die größte Zahl, "n" = Anzahl der Daten, vorne haben! Also:
[mm] $\summe_{a=1}^{n}a*(a-1)/2\in O(n^{3})$
[/mm]
Manchmal reicht es nicht, nur auf die Schleifen(anzahl) zu achten!
Grüße,
Stefan
|
|
|
| |
|
danke für die ausführliche Erläuterung...
mit den Summenzeichen wird das alles viel klarer ...
nochmals vielen Dank
|
|
|
|
