如果代码包含多个 n 复杂度循环，如何计算复杂度？

Question

我对计算复杂性的话题有点困惑。
我知道 Big O 以及如何计算循环的复杂性（也是嵌套的）。

假设我有一个从 1 到 n 运行 3 个循环的程序

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

现在，如果我运行具有 3 个 for 循环的 CPP 代码，是否需要 3*n 时间？

CPP 编译器会同时运行所有 3 个循环还是会一个接一个地运行？
我对这个话题很困惑。请帮忙！

Answer 1

现在，如果我运行具有 3 个 for 循环的 CPP 代码，是否需要 3*n 时间？

是的，假设每次循环迭代的时间相同，但是在 Big O 表示法中O(3*n) == O(n)，因此复杂度仍然是线性的。

CPP 编译器会同时运行所有 3 个循环还是会一个接一个地运行？

隐式并发要求编译器 100% 确保并行化代码不会改变结果。它可以（并且确实如此，请参阅注释）用于简单操作，但cout << i不太可能并行化。然而，它可以以不同的方式进行优化，例如，如果n在编译时已知，编译器可以一次性生成整个字符串并将循环更改为cout << "123456...";.
此外，时间复杂度和并发性是相当不相关的主题。在 20 个线程上执行的代码与在一个线程上执行的代码具有相同的复杂性，只是速度更快（或更快）。