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)。for 循环为 while 循环的每次迭代执行 i 次。现在在 while 循环的每次迭代中 i 递增到 i+i.so 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)。