Laufzeit mit O-Notation < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:12 Mi 12.12.2007 | | Autor: | puky |
| Aufgabe | | Ich soll die Laufzeit mit O-Notation bestimmen. |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Eingabe n
x<-0
für i<-1,2,...,n wiederhole{
für k<-1,2,...,n wiederhole{
x<-x+1
}
für m<-i+1,i+2,...,n wiederhole{
x<-x+1
}
}
Ausgabe x
Ich denk die Laufzeit ist n hoch 5. Bin mir da aber nich so sicher. Könnte auch n hoch 4 sein.
Vieleicht kann mir das ja einer von euch sagen. Und vieleicht noch wie man das mit O-Notation rauskriegt.
fg
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:21 Mi 12.12.2007 | | Autor: | Gilga |
O-Notation ist eine obere Schranke für die Anzahl von Berechnungsschritten! Formal ist jeder Wert der asymptotisch größer oder gleich der Anzahl von Schritten ist eine Lösung.
Ich rechne mal die genaue Anzahl aus. x<-x+1 sei ein Schritt.
für k<-1,2,...,n wiederhole x<-x+1
Du inkrementierst x n-mal => n Schritte
für m<-i+1,i+2,...,n wiederhole x<-x+1
Du inkrementierst x (n-i)-mal => n-i Schritte
Jetzt geh mal die anzahl der schritte für i=1 bis n durch
i=1: (n)+ (n-1)
i=2: (n)+ (n-2)
....
i=n: (n)+ (n-n)
Die addierst du alle
n*n + n*n -(1+2+....+n)
=2*n*n - n*(n-1)/2
=1.5*n*n+0.5*n
[mm] =O(1.5*n^2)
[/mm]
[mm] =O(n^2)
[/mm]
....
|
|
|
|
