O-Notation mit Beweis |
01.02.2011, 16:50 | Auf diesen Beitrag antworten » |
KinueAkachi | O-Notation mit Beweis Meine Frage: Hallo zusammen, folgende Aufgabe: long f(int n) { long result ; if(n < 0) result = -1; else { result = 1; for(int i=0; i < n; i++) { int j = i+1; result = result * j; } } return result ; } 1. Geben Sie die Zeitkomplexität T(0), T(3), T(21) der Methode f an. 2. Geben Sie eine Funktion Z(n) an, die positive n auf die Zeitkomplexität der Methode f abbildet, d.h. Z(n) = T(n) für alle n>=0 3.Geben Sie die kleinste obere Schranke für die Funktion Z(n) aus Aufgabenteil 2 in O-Notation an. Mit Beweis. Meine Ideen: 1. T(0)= 6, T(3)= 24, T(21)= 72 2. Z(n)= 6n + 6 3. Und hier liegt das Problem. O-Notation sollte O(n) sein, aber wie beweise ich? Danke vielmals und noch mehr, wenn ihr in der nächsten Stunde antwortet XD |
|
|