解释一下时间复杂度是O(n)还是O(n^2)？ [重复]

Question

我对时间复杂度有疑问

从用户处获取n

for(int i=0;i<=n;i++){
    //some code
}

时间复杂度为O(n)

for(int i=0;i<=n;i++)
{
    for(int i=0;i<=10;i++)
        //some code
}

时间复杂度是O(n)（从网上看到的）。怎么是O(n)呢。

for(int i=0;i<=10;i++)
{
    for(int i=0;i<=n;i++)
        //some code
}

上述代码的时间复杂度是多少？是 O(n) 还是 O(n^2)？

Answer 1

如果您知道一个进程的时间复杂度为 O(𝑛)，就像您的循环示例一样：

for (int i = 0; i <= n; i++) {
    //some code that has a time complexity of O(1)
}

...然后重复该过程恒定次数，不会改变时间复杂度：

for (int j = 0; j <= 10; j++) {
    for (int i = 0; i <= n; i++) {
        //some code that has a time complexity of O(1)
    }
}

换句话说，O(10𝑛) = O(𝑛)。

您可以在 Wikiepia - Big O notation 上找到一些处理时间复杂度的规则：

乘以常数

令 𝑘 为非零常数。那么𝑂(|𝑘|⋅𝑔)=𝑂(𝑔)。换句话说，如果 𝑓=𝑂(𝑔)，那么 𝑘⋅𝑓=𝑂(𝑔).

Answer 2

如果你不喜欢挥手，你应该应用初等微积分并使用极限定义。因此，如果您代入 f(n) = 10n 和 g(n) = n，您将看到 10 小于无穷大，因此 f(n) = 10n = O(g(n)) 就完成了.