Mit Big O Notation, was ist die richtige Bezeichnung für diesen Algorithmus?

Question

Ich bin gespannt, was ist die offizielle Art, dies mit Big O Notation zu beschreiben?

var prices = [100, 180, 260, 590, 40, 310, 535, 10, 5, 3]; 
var biggest_profit = 0; 

for (var i=0; i < prices.length; i++) { 
    var first_price = prices[i]; 

    for (var j=i+1; j <= prices.length; j++) { 
     // do something here 
    } 
} 

Dies ist das Bit, das mich abwirft:

j=i+1 

Jedes Mal, wenn wir durch i gehen, die j kürzer und kürzer wird.

Wie lautet der korrekte Name für dieses Muster in Big O Notation?

Answer 1

Sie Sigma-Notation kann die Anzahl der Besuche der berechnen innere Schleife ("etwas hier tun")

Dabei folgt (*) aus einer summation rule made famous by the rumour that Gauss once derived it on-the-spot as a young student.

Answer 2

Wenn do something here eine O(1) Operation ist, ist der gesamte Algorithmus O(N^2).

Wie berechnet man? (Danke für Fehler @dfri Fang)

Äußere Schleife: i: [0->N-1]

innere Schleife: j: [i+1->N]

Total = N + (N-1) + (N-2) + (N-3) + ... + 1 = N(N+1)/2 = O(N^2)

Answer 3

Um das große O dieses Algorithmus zu berechnen, stellen Sie sich einfach eine Form vor: In jeder Iteration der äußeren for-Schleife haben wir eine Reihe aus kleinen Quadraten. Jedes Quadrat ist eine Iteration der inneren for-Schleife. Also würden wir für die erste Iteration der äußeren for-Schleife eine volle Reihe von Quadraten haben. Die zweite Reihe verliert eines der Quadrate. Und die dritte Reihe, wird eine andere verlieren. ... Die letzte Reihe, wird nur ein einziges Quadrat haben. Schließlich werden wir diese Form haben:

⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜_____ 
⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜_______ 
⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜________ 
⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜_________ 
⬜⬜⬜⬜⬜⬜⬜⬜⬜__________ 
⬜⬜⬜⬜⬜⬜⬜⬜___________ 
⬜⬜⬜⬜⬜⬜⬜____________ 
⬜⬜⬜⬜⬜⬜_____________ 
⬜⬜⬜⬜⬜______________ 
⬜⬜⬜⬜_______________ 
⬜⬜⬜________________ 
⬜⬜_________________ 
⬜__________________ 

Das ist die Hälfte eines großen Platz. Sein Bereich ist also: prices.length * (prices.length - 1) * 1/2. Und wir können "-1" entfernen, weil es wenig genug ist. Und das Ergebnis: Prices.length * prices.length * 1/2 Die 1/2 ist nicht wichtig in Big O. So hat der Algorithmus eine O (n^2) Zeit Komplexität.