嵌套循环的大 O 表示法

Question

我正在尝试找到此代码的时间复杂度。

for (int i = 0; i <= n - 1; i++)
  for (int j = i + 1; j <= n - 1; j++)
    for (int k = j + 1; k <= n - 1; k++)

我的尝试：我们可以将这个循环写成以下形式：

for (int i = 1; i <= n; i++)
  for (int j = 1; j <= n; j++)
    for (int k = 1; k <= n; k++)

现在这个循环的大哦是 O(n^5)。我是正确的还是做错了什么？

Answer 1

添加了计数器的代码的第一个变体：

int count = 0
for (int i = 0; i <= n - 1; i++)
    for (int j = i + 1; j <= n - 1; j++)
        for (int k = j + 1; k <= n - 1; k++)
            count++;

这计算(i, j, k)与0 <= i < j < k < n 的每个组合。这对应于您可以从n 个元素中选择 3 个元素的方法数，而不考虑它们的顺序。这个数字有一个公式：

        n(n-1)(n-2) / 3！= n ³ /6 - n ² /2 - n/2

第二种变体：

int count = 0
for (int i = 0; i <= n - 1; i++)
    for (int j = 0; j <= n - 1; j++)
        for (int k = 0; k <= n - 1; k++)
            count++;

... 计算您可以从n 个项目中选择 3 个的方法数量，但顺序很重要，并且允许在 3 个选项中重复。这个数字很容易推导出来，因为i、j、k是独立的，每个都可以得到n 个不同的值，所以总数是：

        ñ ³

现在它们代表相同的时间复杂度：

        O(n ³ /6 - n ² /2 - n/2) = O(n ³ )

这是因为大 O的属性：

如果一个函数可能受n 中的多项式约束，那么当n趋于无穷大时，人们可能会忽略多项式的低阶项。

和：

乘以常数
令k为常数。那么：
O(kg) = O(g)如果k非零。