java - 估计算法运行时间的增长顺序

Question

我正在学习在线类(class)，但我不太明白如何估计算法的增长顺序，这里有一个例子

以下代码片段最坏情况运行时间的增长顺序是什么 作为 N 的函数？

   Int sum = 0;
   For (int i = 1; i <= 4*N; i = i*4)
     for (int j = 0; j < i; j++)
    sum++;

谁能告诉我如何获得它

Answer 1

只需计算语句 sum++; 被执行了多少次。

= 1 + 4 + 16 + 64 ... + 4*N

这是一个公因数为 4 的等比级数。如果该级数的项数为 k，则

4^k = 4*N.

Sum of series = (4^k - 1)(4-1) = (4*N - 1)/3.

按照增长顺序，我们忽略了恒定因素。

因此复杂度为 O(N)。