算法分析

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)