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

Question

Читают «Структуры данных и алгоритмы» из Ахо, Hopcroft & Ульмана, и я запутался с физическими упражнениями 1.12 B:

Что вычислительная сложность (выраженной в Big O точках) эта процедура Паскаля?

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).