c++ 时间复杂度是O(1)还是O(n)?

hfsqlsce  于 9个月前  发布在  其他
关注(0)|答案(1)|浏览(128)

已关闭。此问题需要details or clarity。目前不接受回答。
**要改进此问题吗?**通过editing this post添加详细信息并阐明问题。

3天前关闭。
Improve this question

#include <bits/stdc++.h>
using namesppace std;

int main() {
    int n = 100;
    for(int i = 0; i < n; i++) {
        cout << "hello";
    }
}

我认为它将是O(n)而不是O(1),因为循环执行n次迭代。对于人们说它是O(1),因为n是常数,如果n=1e9呢?它仍然是O(1)吗?因为n是常数?

0dxa2lsx

0dxa2lsx1#

让我们考虑两个例子:

void myFunc(int n) {
    for (int i = 0; i < n; i++) {
        cout << "hello";
    }
}

个字符
在第一个例子中,复杂度将是O(n),因为如果你用一个10倍大的变量n调用这个函数,循环中的代码将执行10倍多的迭代。
在第二个例子中,复杂度将是O(1),因为代码执行的命令数量不取决于传递到函数中的变量。
然而,在这两种情况下,复杂度都可以被认为是O(n);只是在第二种情况下,n是一个常数,所以O(const) = O(1)
(This只是为了清楚起见。如果你不想让对方感到困惑,你不应该在这里说复杂性是O(n)
你也可以说:
代码

for (int i = 0; i < n; i++) {
    cout << "hello";
}


的复杂度为O(n),但如果加上变量n的初始化,则代码

int n = 100;
for (int i = 0; i < n; i++) {
    cout << "hello";
}


复杂度为O(1)

相关问题