algorithm - 嵌套循环的大 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++)

现在这个循环的大 Oh 是 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 个元素的方式的数量，而不考虑它们的顺序。有 a formula对于那个数字:

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 个不同的值，所以这个数字很容易得出，所以总数是:

n³

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

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

这是因为 properties of big O :

if a function may be bounded by a polynomial in n, then as n tends to infinity, one may disregard lower-order terms of the polynomial.

和:

Multiplication by a constant
Let k be a constant. Then:
O(kg) = O(g) if k is nonzero.