algorithm - 确定算法的复杂度

假设ALGO（p）是一个采用θ（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），我不知道这会对事情产生什么影响。

最佳答案

它是大θ（n）：
它调用algo(p)O（logn）次，p=1，2，4，…，2^（floor（logn））。
这是θ（1+2+…+2^（楼层（logn））=θ（2^（楼层（logn+1）-1）=θ（n）。