algorithm - 如何计算两个循环的时间复杂度（动作数）？

Question

我不确定如何计算两个循环的时间复杂度。

我从 1 运行到 n：1,2,3,4,5,...,n

j 从 1 到 i；1,2,4,8,...,我

当 i = 1
j：1
循环运行：1 次

当 i = 2
j：1,2
循环运行：2 次

当 i = 3
j：1,2
循环运行：2 次

当 i = 4
j: 1,2,4
循环运行: 3 次

当 i = 5
j: 1,2,4
循环运行: 3 次
.... 当 i = n
j: 1,2,4,8,...,n 循环运行: logn+1 次

所以循环运行（次数）：1+2+2+3+3+3+3+4+...+(logn+1)

所以我不明白这种恒常性。
我怎样才能创建这个的西格玛？

Answer 1

由于您正在尝试为您的周期评估 Big-O 并且没有其他依赖项，因此您可以使用以下估计：

O(Full Cycle) = O(Outer Cycle)*O(Inner Cycle) = O(N)*O(log2(N)) = O(N log(N))

（根据定义，第二次估计很简单，因为我们正在寻找大 O 并且我们知道循环将迭代直到j*2 < i并且也i < n）