for (int i = 0; i < n; ++i ) { //n
for (int j = 0; j < i; ++j) { //n
cout<< i* j<<endl;
cout<< ("j = " + j);
}
for (int k = 0; k < n * 3; ++k) //n?
cout<<"k = " + k);
}
在这个循环中，我看到第一个 for 循环是 O(n)，第二个循环也是 O(n) 但第三个 for 循环让我感到困惑。K 小于扩展的东西，对于这个循环，这也是 O(n) 吗？如果是这样，在这种情况下，另一个循环的时间复杂度内的两个循环是什么？我假设 O(n^2) 由于中间的两个 n 没有以任何方式相乘。这样对吗？另外，如果我是正确的并且第二个循环是 O(n)，那么如果它是 O(logn)，时间复杂度是多少？
（不是作业，只是为了理解目的）
大 O 符号的一个很好的经验法则如下：
如有疑问，请由内而外工作！
在这里，让我们从分析两个内部循环开始，然后向外工作以获得整体时间复杂度。此处显示了两个内部循环：
for (int j = 0; j < i; ++j) {
cout<< i* j<<endl;
cout<< (”j = ” + j);
}
for (int k = 0; k < n * 3; ++k)
cout<<”k = ” + k);
第一个循环运行 O(i) 次，每次迭代执行 O(1) 工作，因此它总共执行 O(i) 工作。第二个循环运行 O(n) 次（它运行 3n 次，并且由于大 O 表示法咀嚼常量，因此总次数为 O(n)）并且每次迭代执行 O(1) 工作，因此它执行 O(n)总工作。这意味着您的整个循环可以重写为
for (int i = 0; i < n; ++i) {
do O(i) work;
do O(n) work;
}
如果你做 O(i) 工作然后做 O(n) 工作，完成的总工作是 O(i + n)，所以我们可以更进一步地将其重写为
for (int i = 0; i < n; ++i) {
do O(i + n) work;
}
如果我们查看这里的循环边界，我们可以看到 i 的范围从 0 到 n-1，因此 i 永远不会大于 n。因此，O(i + n) 项等效于 O(n) 项，因为 i + n = O(n)。这使得我们的整体循环
for (int i = 0; i < n; ++i) {
do O(n) work;
}
从这里开始，整体运行时间是 O(n 2 )应该更清楚一点，所以我们进行 O(n) 次迭代，每次迭代总共完成 O(n) 次工作。
您在另一个答案的评论中询问如果第二个嵌套循环仅运行 O(log n) 次而不是 O(n) 次会发生什么。这是一个很好的练习，所以让我们看看如果我们尝试一下会发生什么！
想象一下代码是这样的：
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
cout<< i* j<<endl;
cout<< ("j = " + j);
}
for (int k = 0; k < n; k *= 2)
cout<<"k = " + k);
}
在这里，第二个循环只运行 O(log n) 次，因为 k 呈几何增长。让我们再次应用从内到外工作的想法。内部现在由这两个循环组成：
for (int j = 0; j < i; ++j) {
cout<< i* j<<endl;
cout<< ("j = " + j);
}
for (int k = 0; k < n; k *= 2)
cout<<"k = " + k);
这里，第一个循环在 O(i) 时间运行（和以前一样），新循环在 O(log n) 时间运行，所以每次迭代完成的总工作是 O(i + log n)。如果我们使用这个重写我们的原始循环，我们会得到这样的结果：
for (int i = 0; i < n; ++i) {
do O(i + log n) work;
}
这个分析起来有点棘手，因为 i 从循环的一次迭代更改为下一次。在这种情况下，通常不是通过将每次迭代完成的工作乘以迭代次数来进行分析，而是通过将循环迭代中完成的工作相加来进行分析。如果我们在这里这样做，我们将看到完成的工作与
(0 + log n) + (1 + log n) + (2 + log n) + ... + (n-1 + log n)。
如果我们重新组合这些术语，我们得到
(0 + 1 + 2 + ... + n - 1) + (log n + log n + ... + log n) （n 次）
这简化为
(0 + 1 + 2 + ... + n - 1) + n log n
求和的第一部分是高斯著名的和 0 + 1 + 2 + ... + n - 1，恰好等于 n(n-1) / 2。（知道这一点很好！）这意味着我们可以将完成的总工作重写为
n(n - 1) / 2 + n log n
= O(n 2 ) + O(n log n)
= O(n 2 )
最后一步是因为 O(n log n) 由 O(n 2 ) 项支配。
希望这可以向您展示结果的来源以及如何得出结果。从内到外工作，计算出每个循环做了多少工作，并用更简单的“做 O(X) 工作”语句替换它，使事情更容易理解。当你有一些工作量随着循环计数器的变化而变化时，有时通过限制值并显示它永远不会离开某个范围来解决问题是最容易的，而有时通过明确计算出多少来解决问题是最容易的工作是从一个循环迭代到下一个循环迭代完成的。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句