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