算法分析

Question

所以我理解了一些算法分析，但是我完全不知道如何做这个。有人能给我解释一下吗？这会是O(logn)吗？

for (int i=1; i < n; i*=2)
for (int j=0; j < i; j++)
// do simple operation

Answer 1

要找到嵌套循环的大O，需要执行如下步骤。

例如，让：

n = 10

现在，外部循环执行3次，即：

i=2,4 and 8

内部循环在每次迭代中执行3次，如下

i=2 it iterates 2 times
i=4 it iterates 4 times
i=8 it iterates 8 times

因此，迭代的总次数小于2*n，使得它成为O(2n)，我们可以忽略常数因子，所以它的大O是

O(n)

Answer 2

那实际上是O(n)

您可以如下所示：

• 操作数为系列2、4、8、16、32、.就在n之前。
• 这个几何级数的和大约在从n到2n的范围内。
• 因此，整个算法是O(n)，因为您可以忽略常量因子。

Answer 3

我将首先计算小-o，让你了解整个过程，然后我们从它得到大-O。

让我们把它分成几部分：

for (int i=2; i < n; i*=2)

首先，我们从i=2得到了一个绑定

如果i*=2然后i ={2，4，8，16，32，64.} so i增量在2^x之后，那么：

我们正在寻找i > n为真，所以2^x > n必须是真的，做一些数学运算：

log2(2^x) = log2(n)

x=log2(n) //这里我们发现i需要log2(n)循环来满足条件语句。

因为在for中，我们有比较和界，所以对于这个for，它将是2log2(n)+1操作。

注意:由于这是一个嵌套链，下面的for中的每个操作都将乘以2log2(n)+1次数

for (int j=0; j < i; j++)

j=0 1界

因此，j={0,1,2,3,4,5,6,7,8....} j++ j=n，然后是2n+1，用于这个for

最后，我们有一个小o等于：

(2n+1)*(2log2(n)+1)

4 2log2 2(N)+ 2n +2log 2(N)+ 1

log2(n)(4n+2) +2n +1

结果表明，o(log2(n)(4n+2) +2n +1)，为了得到大O，我们可以减少这个表达式，忽略一些因素，然后：

O(log2(n)n)

希望这是足够清楚的理解。

致以问候。