Какова временная сложность этой паскальской программы? - PullRequest
Новая
       10

Какова временная сложность этой паскальской программы?

0 голосов
/ 26 июня 2018 
Function what(x, n:integer): integer:
Var
    value : integer
begin
    value := 1
    if n > 0 then
    begin
        if n mod 2 =1 then
            value := value * x;
        value := value * what(x*x, n div 2);
    end;
    what := value;
end;

Это вычисляет x<sup>n</sup> и имеет сложность времени O(log N).

Пожалуйста, объясните, как сложность времени и как она O(log N)?

1 Ответ

0 голосов
/ 26 июня 2018

Достаточно просто.На каждом уровне рекурсии вы вызываете следующий уровень, передавая half из n: 

what(x*x, n div 2);

Поскольку именно это значение определяет, сколько вызовов сделано, это O(log N) сложность.

Например, если вы начали с 64, вы бы назвали его с помощью 64, 32, 16, 8, 4, 2, 1 и 0 (восемь раз).Начало с 128 приведет только к одному дополнительному уровню рекурсии.

Если вы подумаете о похожем (нерекурсивном) случае, он может стать более понятным: 

function oLogN(n):
    while n > 0:
        n = truncate(n / 2)

Это в основном то, к чему сводится ваш код, с различными значениями n, принимающими другое число steps согласно: 

                              SEQUENCE
    n   steps   lowest n          | highest n (if different)
-----   -----   ------------------+-------------------------
    0       0                   0 |
    1       1                1, 0 |
  2-3       2             2, 1, 0 |                  3, 1, 0
  4-7       3          4, 2, 1, 0 |               7, 3, 1, 0
 8-15       4       8, 4, 2, 1, 0 |           15, 7, 3, 1, 0
16-31       5   16, 8, 4, 2, 1, 0 |       31, 15, 7, 3, 1, 0
32-63       6              ... and so on
...