упражнение по вычислительной сложности - PullRequest
Новая
       9

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

4 голосов
/ 20 марта 2009

Я читаю «Структуры данных и алгоритмы» от Aho, Hopcroft & Ullman, и меня смущает упражнение 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

Не могли бы вы мне помочь?

Спасибо!

1 Ответ

6 голосов
/ 20 марта 2009

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

В этом случае внутренний оператор выполняется раз пропорционально (n 3 ). я запускаю от 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 3 ).

...