Rechenkomplexität Übung

Question

ich „Datenstrukturen und Algorithmen“ von Aho, Hopcroft & Ullman, und ich bin verwirrt mit Übung 1.12 B Lesen:

, die die Berechnungskomplexität (in Big O-Notation ausgedrückt) von diese Pascal-Prozedur?

procedure mysterious(n: integer); 
    var 
     i, j, k: integer; 
    begin 
     for i := 1 to n - 1 do 
      for j := i + 1 to n do 
       for k := 1 to j do 
        {mysterious statement of O(1)} 
    end 

Könnten Sie mir bitte helfen?

Danke!

Answer 1

Es ist O (n). Das große O zeigt, wie die Ausführungszeit (oder der Speicher oder was auch immer) proportional zur Größe der Aufgabe ist (der Proportionalitätskoeffizient wird weggelassen).

In diesem Fall wird die innere Anweisung mal proportional ausgeführt (n). Ich laufe von 1 bis (n-1) - also wird alles innerhalb des äußeren Zyklus (n-1) mal ausgeführt. j läuft im Durchschnitt von (n/2) bis (n) - so wird alles innerhalb (n-1) * (n/2) mal ausgeführt. k läuft im Durchschnitt von 1 bis (3/4 * n). Dies führt zu (n-1) * (n/2) * (3/4 * n-1) Ausführungen der inneren Aussage. Dies ist O (n).