упражнение на вычислительную сложность

Question

Я читаю "Структуры данных и алгоритмы" от Ахо, Хопкрофта и Ульмана, и меня смущает упражнение 1.12 B:

Какова вычислительная сложность (выраженная в обозначении Big O) этой процедуры на языке Pascal?

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

Не могли бы вы, пожалуйста, помочь мне?

Спасибо!

Answer 1

Это O(n³).Big-O показывает, как время выполнения (или память, или что-то еще) пропорционально размеру задачи (коэффициент пропорциональности опущен).

В этом случае внутренний оператор выполняется раз, пропорциональный (n³).i выполняется от 1 до (n-1) - таким образом, все внутри внешнего цикла выполняется (n-1) раз.j выполняется в среднем от (n/ 2) до (n) - таким образом, все внутри выполняется (n-1) * (n / 2) раз.k работает в среднем от 1 до (3/4* n).Это приводит к (n-1)* (n / 2)* (3/4 * n-1) выполнению внутреннего оператора.Это O(n³).