算法设计与分析求解加法执行次数

Question

输入： n=2^t，t为正整数
输出：k
k←1
while n≥1 do
for j←1 to n do
k←k+1
n←n/2
return k
我算出来是2n-2不知道对不

Answer 1

将for拆解后再算：

for (A;B;C) D;
//等价于
{
 A;
 while (1) {
  if (!(B)) break;
  D;
  C;
 }
}