0

有一个关于这个步数问题的问题。我想我有基本的想法，但很难把数学直接写在纸上。首先是伪代码：

for i = 1 to n
    x = x + 1
    j = n
    while (j>1)
        j = j/2

和我的解释：

n/2 + 1

n/2

n/2

n/2 <-- 第 4 行求和的顶部（while 循环）

Σlogn+2

i=1 <-- 第 4 行求和的底部（while 循环）

n/2 <-- 第 5 行求和的顶部（while 循环的主体）

Σlogn+1

i=1 <-- 第 5 行求和的底部（while 循环的主体）

所以步数的前三行看起来不错，但是循环内的两个求和对我来说有点棘手。所以对于第一个 logn + 2 我可以分为两个步骤：

n/2

Σ 2

我=1

和

n/2

Σ 登录

我=1

所以我习惯于处理 n 的直接求和，而不是 n/2。但我会快速尝试一下。

2*((n^2+n)/2) 或者更确切地说只是去掉这个分数，所以它是直的：n^2+n。

然后对于 logn 部分：

logn*((n^2+n)/2) = ? 现在我不太确定。不确定这是否会简化。如果有人对此有任何建议，我将不胜感激，但我认为我得到的就是这一半。因此，我将两者结合起来，得到伪代码第 4 行总和的最终答案：

登录 * (n^2+n)/2 + n^2 + n

对于第二个总结，我认为它将是：

登录 * n^2 + n

（可以从我上面已经完成的内容中借一点。只是放弃了我有 2 * (n^2+n)/2 的部分，而是我将简单地拥有两组一半，它们组合成一个 n^ 2+n 如果我认为这有意义吗？

如果我完全失去了它，请告诉我。谢谢！！

4

1 回答 1

0

我觉得你的分析有点不对劲。首先，请注意循环体中发生的事情与orfor的值无关。所以循环执行次数和每次循环体中发生的步数相同。循环体执行 floor(log 2 (n)) 次。这就是所有需要的分析。结果是 n*floor(log 2 (n))。（如果“步骤”是指语句执行，则需要稍微修改一下以考虑每个循环体中的语句数。）ixfornforwhile

于 2012-11-18T09:04:18.680 回答