algorithm - 简单程序的复杂性

Question

我有一个程序:

procedure A(n) 
begin 
 i:=j:=1
 while i < n do begin 
     i:=i+i
     for k:=1 to i do j:=j+1
 end
end

我的问题是 - 我知道 while 循环运行 log(n) 次，但我不确定整个程序运行了多少次？在此先感谢您的时间!

Answer 1

while 循环执行了 log(Base2)n -1 次。所以它是 O(log(Base2)n)。对于 while 循环的每次迭代，for 循环执行 i 次。现在在 while 循环的每次迭代中，我递增到 i+i。所以 for 循环迭代的总数=1+2+4+8+...2 ^(log(Base2)n-1)=2^((log(base2)n-1)+1)-1/2-1=n-1.so for 循环是 O(n)。所以总时间复杂度=O(log(Base2)n+O(n)=O(n)。