嵌套循环的时间复杂度，其中 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

假设内部语句花费常数时间。

内部循环运行s (j-1)次，因此其运行时间为

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

中间循环运行s 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)

外层循环运行s 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).

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

Time complexity of nested loops where k < j < i < n

algorithm

big-o

time-complexity

asymptotic-complexity