algorithm - 确定算法的复杂度

Question

假设 algo(p) 是一种算法，它需要 Theta(p) 时间来执行并且不会改变 p。确定以下算法的运行时间复杂度：

Algo2(n) 
begin
p=1;
while p <= n 
    begin 
    algo(p)
    p=2*p
    end;
end;

真的不知道从哪里开始，我想 O(logn) 可能是因为 p=p*2 但是在 while 循环中有一个 algo(p) ，我不知道这会如何影响事情。

Answer 1

这是大 Theta（n）：

它调用algo(p)O(logn) 次，p = 1, 2, 4, ..., 2^(floor(logn))。这是 Theta(1 + 2 + ... + 2^(floor(logn)) = Theta(2^(floor(logn+1)-1) = Theta(n)。

Answer 2

为了解决更简单的问题，您可以这样设置：

Algo(n)
  begin
  p=1, i=1
  while p<= n
    begin
    algo(p)
    p=2*p
    i++
    end
  end

你可以这样重写：

Algo(n)
  begin
  i=1
  while 2^(i-1)<=n
    begin
    algo(2^(i-1))
    i++
    end
  end

然后，正如 Henrik 所说：

它以 p = 1, 2, 4, ..., 2^(floor(logn)) 调用 algo(p) O(logn) 次。这是 Theta(1 + 2 + ... + 2^(floor(logn)) = Theta(2^(floor(logn+1)-1) = Theta(n)。