三重循环的 Theta 运行时间，本质上远小于 n^3

Question

我今天在看一个编程问题，但在查找它的 theta 运行时时遇到了问题。基本上，在我的问题中，我形成了以下循环结构：

for(int i = 0; i < n; i++)
    for(int j = i + 1; j < n; j++)
        for(int k = j + 1; k < n; k++)
            //check some condition

显然是O(n^3)。更准确地说，是o(n^3)。但是，我想知道这是什么 theta 运行时。如果你检查这个循环，内部条件执行的实际次数是 n!/3!(n-3)!因为它正在评估 n 个数字的所有组合而不重复。

除了 n choose r 之外，还有其他方法可以用多项式形式表示 theta 运行时间吗？

例如，选择排序的运行时间（类似但只有 2 个 for 循环）可以通过查看正在执行的指令数来评估。 n + (n-1) + (n-2) ... + 1 将简化为 n(n+1) / 2.

Answer 1

n!/3!(n-3)! = n(n-1)(n-2)/3! = (n^2-n)(n-2)/6 = (n^3-2n^2-n^2+2n)/6 
            = (n^3 -3n^2 + 2n)/6

您可以很容易地证明¹ 对于足够大的 n 值：

1/2 n^3 < (n^3 -3n^2 + 2n)/6 < 2n^3

所以当谈到渐近符号时，它在 Theta(n^3) 中，而不是在 o(n^3) 中。

(1) 一种显示方式是：

lim 1/2n^3 /  ((n^3 -3n^2 + 2n)/6)  when n->infinity = 1/2 < infinity

另一个不等式也是如此

Theta Runtime of a triple loop that essentially much less than n^3