这个循环的时间复杂度是多少？

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 是常数？

Answer 1

让我们考虑两个例子：

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

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

在第一个示例中，复杂度将为

O(n)

，因为如果您使用 10 倍大的变量

n

调用此函数，循环内的代码将执行 10 倍以上的迭代。

在第二个示例中，复杂度将为

O(1)

，因为代码执行的命令数量不取决于传递到函数中的变量。

但是，在这两种情况下，都可以考虑复杂性

O(n)

；只是在第二种情况下，

n

是一个常数，所以

O(const) = O(1)

。

---

你也可以说：

代码

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)

。