algorithm - 这个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

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

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