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)
InformationsquelleAutor Josh | 2011-10-28
Schreibe einen Kommentar