Asymptotic Analyse von drei for-Schleifen verschachtelt

Ich möchte die Theta-Komplexität dieses verschachtelten for-Schleife berechnen:Asymptotic Analyse von drei for-Schleifen verschachtelt

for (int i = 0; i < n; i++) { 
     for (int j = 0; j < i; j++) { 
      for (int k = 0; k < j; k++) { 
       // statement

Ich würde sagen, es ist n^3, aber ich glaube nicht, das ist richtig, denn Jede for-Schleife geht nicht von 1 nach n. Ich habe einige Tests:

n = 5 -> 10

10 -> 120

30 -> 4060

50 -> 19600

So muss es zwischen n sein^2 und n^3. Ich habe versucht, die Summenformel und so, aber meine Ergebnisse sind viel zu hoch. Obwohl von n^2 log (n), aber das ist auch falsch ...

Quelle

2013-02-24 Aaron

Es ist O(N^3). Die genaue Formel ist (N*(N+1)*(N+2))/6

Quelle

2013-02-24 14:17:56 dasblinkenlight

Haben Sie etwas dagegen erklärt, wie man diese bekommen? – Aaron

@Aaron Ich fragte Wolfram Alpha (siehe den Link in der Antwort), es ist gut bei diesen Arten von Berechnungen. – dasblinkenlight

Ja, das habe ich gesehen, aber ich möchte verstehen, warum es diese Formel ist. – Aaron

Mit Sigma Notation ist ein effizienter Schritt für Schritt Methodik:

Quelle

2014-05-01 16:52:20

Asymptotic Analyse von drei for-Schleifen verschachtelt

Antwort

Verwandte Themen