嵌套循环的时间复杂度，其中k <j <i <n

Question

我想知道此算法的时间复杂度以及它如何计算。

for (i = 1; i < 2n; i++) { 
    for (j = 1; j < i; j++) { 
     for (k = 1; k < j; k++) { 
      // do something 
     } 
    } 
} 

Answer 1

假设内部语句需要一定的时间。

内循环运行(j-1)倍，因此它的运行时间是

t_inner(j) = Sum {k from 1 to j-1} 1 
      = j-1 

中间循环运行i-1倍。其运行时间为：

t_middle(i) = Sum { j from 1 to i-1 } t_inner(j) 
      = Sum { j from 1 to i-1 } j-1 
      = 1/2 * (2 - 3 * i + i^2) 

外环运行2n-1次。它的运行时间是：

t_outer(n) = Sum { i from 1 to 2n-1 } t_middle(i) 
      = Sum { i from 1 to 2n-1 } 1/2 * (2 - 3 * i + i^2) 
      = 1/3 (-3 + 11 n - 12 n^2 + 4 n^3) 

从最后一个公式，我们可以看到，时间复杂度为O(n^3)。