寻找嵌套循环结构的大 O

Question

我有一个类似于下图所示的循环。我有兴趣为这个循环结构寻找 Big O。

for i = 1 to n { // assume that n is input size
                         ...
                         for j = 1 to 2 * i {
                             ...
                             k = j;
                                 while (k >= 0) {
                                     ...
                                     k = k - 1;
                                 }
                         }
               }

据我所知：

最外层循环运行 'n' 次
第二个循环运行 '2n' 次（假设增量大小为 1）
最内层循环运行“2n”次

那么 n 的大 O 应该是 O(n^3) 还是会有所不同？

对于此类问题及其解决方案的具体 link 将不胜感激。

Answer 1

设I()、M()、T()为内层循环、中间循环和整个程序（最外层循环）的运行次。如果我们从内到外工作，我们得到：

Inner-most loop;
I(j) = Summation (1) //from k=0 to j
I(j) = j+1  //Using basic Summation expansion formula.

Middle loop
M(i) = Summation (I(j)) //from j=1 to 2i
M(i) = Summation (j+1)  //from j=1 to j=2i with I(j)'s values
M(i) = Summation (j) + Summation (1)  //both from j=1 to j=2i

Using the expansion formula for Summation (j) from j=1 to n is '(n(n+1)/2)' and the fact that Summation (1) from j=1 to n is 'n', we get:

M(i) = 2i^2 + 3i

Outer-most loop:

T(n) = Summation (2i^2 + 3i)  //Summation from i=1 to n
T(n) = Summation (2i^2) + Summation (3i)  //both summations from i=1 to n
T(n) = 2*Summation (2i^2) + 3*Summation (i)  //both summations from i=1 to n
T(n) = (2(2n^3 + 3n^2 + n))/6) + (3(n(n+1))/2)  //using summation expansion formulas
T(n) = (4n^3 + 15n^2 + 11n)/2

Which means Big O of n be T(n^3).

注：求和展开的基本求和展开公式可以在this首页找到link

感谢@Paul Hankin 的提示

寻找嵌套循环结构的大 O

Finding the Big O of a nested loop Structure

algorithm

big-o