计算嵌套循环的大O

本文介绍了计算嵌套循环的大O的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我在计算以下代码的大O时遇到问题。我从来都不是最聪明的饼干。 有谁能解释一下吗。由于嵌套循环，我在这里的猜测是O(N^2)，但我知道还有更多原因。

static inline int f1 (int a, int b) { for (int c = 0; c < b; c++) { a -= n; } return a; } int f2 (int n) { int r = n * n * n; for (double i = n; i >= 0; i -= 2) { r = f1(r, i); } return r; } 推荐答案

首先，请注意F1的运行时完全依赖于第二个参数，该参数控制循环迭代的次数。因此，它的运行时在第二个参数中是线性的。

接下来，注意f2中的循环运行n/2次，其中i取值0、2、4、6、...、n。因为i是f1的第二个参数，所以运行时间由

给出

0+2+4+...+n

=2(0+1+2+.+n)

=2&theta；(n^2)

=&Theta；(n^2)

所以运行时是&theta；(n^2)。请注意，几乎所有其他事情都是为了让你分心，意在误导你。只关注控制迭代和循环的变量会揭示您需要关注的实际逻辑。

希望这能有所帮助！