根据n确定函数执行变量计数递增的频率

根据n确定函数执行变量计数递增的频率

这种练习的目的是教您如何在纸上进行分析，而不是在机器上运行。但是，让我们看一下模式：

• 外环将运行总计

  n

  次
• 内部循环将在1到2

  n

  倍之间运行，具体取决于

  i

  当时的状态。但是您知道平均而言，这将运行

  (n+1)/2

  时间。
• 因此

  count = n(n+1)/2)

  ，这是

  O(n^2)

见算术级数

更新： 根据要求-为什么内循环是

(n+1)/2

：

外循环将使i在1和n之间递增。因此，在外循环的每次迭代中，内循环将比以前“循环”更多。

因此，内部循环将迭代此次数：

• 1 + 2 + 3 + … + n

因此，我们可以做一些聪明的事情并配对：

• n与1：（n + 1）= n + 1
• n-1与2：（n-1）+ 2 = n + 1
• n-2与3：（n-2）+ 3 = n + 1
• …

由于我们将它们配对，所以我们有n / 2个这样的对：

• 因此1 + 2 + … + n的总和为（（n + 1）*（n / 2））。
• 因此平均值为（（n + 1）*（n / 2））/ n =（n + 1）/ 2

（在长条纸上书写1 + 2 + 3 + … + n时将其可视化，然后将其对折。）

我也强烈建议您阅读有关卡尔·弗里德里希·高斯（Karl Friedrich
Gauss）的著名故事，
以便您永远记住如何对算术级数求和=）