想知道算法的时间复杂度

Question

在我的工作中，我必须实现一个算法，具体细节并不重要，但我无法对这个特定算法的时间复杂度有一个明确的答案。

简而言之，它看起来像这样：

for(let i = 0; i < 3; i++) {
    for(let j = 0; j < n - 1; j++) {
        for(let k = 0; k < 8; k++ {
            // Do some stuff
        }
    }
}

这个算法的时间复杂度是多少？

一开始我以为会是 O(n^3) 之类的。但我想得越多，我就越认为它实际上更像是一个 0(n)。因为，尽管我们有 3 个 for 循环，但只有一个可以是可变大小的，另外两个是恒定的。

那么这个算法的实际时间复杂度是多少呢？是 O(n^3)、O(n) 还是其他？

Answer 1

是的，时间复杂度为O(n)。你是对的。

总执行次数为 3 * n * 8 = 24*n，其中对于较大的 n 可以忽略 24。所以复杂度是O(n)

Answer 2

直接答案

除了已经给出的很好的答案之外，我希望您能够描绘每个循环的计算：

某些隐式规则与：

• 应用的 常数 k 为 O(1)

示例：3 = O(1)、8 = O (1)

• 给定一个变量 n 和一个常量 k 的高值，关系为已验证：O(n + k) = O(n) + k = O(n)

示例：O(n-1) = O(n) -1 = O(n)

• 给定变量的高值 n 和常数 k，验证关系：kx O(n) = O(kn) = O(n)

示例：<代码>3x O(n) = O(3n) = O(n)

扩展

让我们改变你的循环，让你有 O(n^3) 正如你想知道的那样：

for(let i = 0; i < n-1; i++) {
    for(let j = 0; j < n - 1; j++) {
        for(let k = 0; k < n-1; k++ {
            // Do some stuff
        }
    }
}

因为每个循环都有复杂度为 O(n)，我们有 O(n) x O(n) x O(n) = O(n^3)

Answer 3

代码的时间复杂度为 O(n)：

由于外循环迭代固定次数，因此内循环每次迭代 n - 1 次，并且对于其中的每一次，最内层的循环都会迭代恒定的次数。

因此，您得到 3 * (n - 1) * 8 = 24n - 24，并且由于常量被大 O 表示法丢弃，您得到 O(n)。

话虽这么说，代码的时间复杂度可能会受到最内层循环内部运行的代码（即 // Do some stuff 部分）的影响。如果您只在那里执行固定数量的操作，则代码复杂性不会受到影响。但是，例如，如果您在其中对大小为 n 的数组进行排序，那么这会将时间复杂度更改为 n * nlogn。

Answer 4

此代码的时间复杂度为 O(n)。外部和内部循环具有恒定的迭代次数，并且与输入大小 (n) 无关。对于大 O 表示法，常量将被丢弃。

Answer 5

时间复杂度将为O(n)，因为 3 和 8 是可以忽略的常量。另外，第二个循环将持续到 n - 1，其中 1 也被忽略。注意：当 n 的值变得非常大时，就会出现对常量的无知。

如果在所有这些循环中调用一个函数，那么对该函数的总调用次数为 n，但精确地说，总调用次数将是

(8 * 3 * n) - ((8 * 3) - 1)

我们在大 O 表示法中忽略的。

在 C 中尝试以下代码：

#include <stdio.h>

size_t my_calls = 1;

void call_me(void){
    my_calls += 1;
}

int main(void)
{
    size_t n = 1000; // let n = 1000

    for(size_t i = 0; i < 3; i++) 
    {
        for(size_t j = 0; j < n - 1; j++) 
        {
            for(size_t k = 0; k < 8; k++) 
            {
                call_me();
            }
        }
    }
    printf("Total calls %lu\n", my_calls);
    if(my_calls == (8 * 3 * n ) - ((8 * 3) - 1))
        printf("GOOD\n");
    else
        printf("BAD\n");
    return 0;
}

实时演示< /strong>