Die Berechnung von T(n) Zeitkomplexität eines Algorithmus
Ich bin auf der Suche nach Klärung in der Entwicklung der Zeit, die Effizienz eines Algorithmus, insbesondere T(n). Der Algorithmus ist unten nicht so effizient wie es sein könnte, aber es ist ein gutes Beispiel zu lernen, glaube ich. Ich würde mich über eine line-by-line-Bestätigung der Summe der Operationen in den code:
Pseudo-code
1. Input: array X of size n
2. Let A = an empty array of size n
3. For i = 0 to n-1
4. Let s = x[0]
5. For j = 0 to i
6. Let sum = sum + x[j]
7. End For
8. Let A[i] = sum /(i+1)
9. End For
10. Output: Array A
Mein Versuch bei der Berechnung von T(n)
1. 1
2. n
3. n
4. n(2)
5. n(n-1)
6. n(5n)
7. -
8. n(6)
9. -
10. 1
T(n) = 1 + n + n + 2n + n^2 - n + 5n^2 + 6n + 1
= 6n^2 + 9n + 2
So, T(n) = 6n^2 + 9n + 2 ist das, was ich erwarte, von diesem ich ableiten Big-O von O(n^2).
Welche Fehler, wenn überhaupt habe ich in meiner Berechnung...
Edit: ...im zählen der primitiven Operationen ableiten von T(n)?
- Es ist ein straight-forward-Doppel-loop ohne bedingte Pausen, so ist es
O(n^2)
okay... - Danke, ich war in wenig Zweifel, dass es war nicht O(n^2), nur ein wenig unsicher über die calucations vorher für T(n)
Du musst angemeldet sein, um einen Kommentar abzugeben.
Ihr Ergebnis O(n^2) ist korrekt und wird durch die zwei verschachtelten Schleifen. Ich würde lieber die Ableitung wie
folgt, dass aus der Beobachtung der verschachtelten Schleifen.
Bin ich nicht wirklich sicher auf Ihre Methodik, aber O(n^2) scheint korrekt zu sein. Bei jeder iteration der ersten Schleife Sie ein sub-Schleife von der vorherigen Elemente. Daher sucht man bei 1 das erste mal 2 der zweite dann 3, dann... dann n der letzten Zeit. Dies ist äquivalent zu der Summe von 1 bis n, die Ihnen die Komplexität von n^2.