c++ - 如果代码包含多个 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

Now if I ran my CPP code having 3 for loops, will it take 3*n time?

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

Will the CPP compiler run all the 3 loops at the same time or will do it one after another?

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