这个pascal程序的时间复杂度是多少？

Question

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

Answer 1

相当简单。在每个递归级别，您调用下一个级别，传入 half of n:

what(x*x, n div 2);

由于是该值控制调用的次数，因此它具有 O(log N) 的复杂性。

例如，如果您以 64 开头，则可以用 64、32、16、8、[=20 来调用它=]、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

这个pascal程序的时间复杂度是多少？

what is the time complexity of this pascal program?

algorithm

pascal

time-complexity