确定作为n的函数，执行增加变量计数的语句的频率
好的，我是分析算法的新手，非常感谢任何有用的技巧，可以分享如何解决这个问题。 我试图确定计数增加的次数是n的函数。 我在一个ide中运行它，对于值1-7，输出为1,3,6,10,15,21,28。 我只是不确定如何写这个作为n的函数？ 谢谢。 循环如下：
for(int i = 1 ; i <= n ; i++){ for (int j = 1 ; j <= i ; j++) { count++; } } 这种练习的目的是教你如何在纸上分析它而不是在机器上运行它。 但让我们来看看这个模式：
- 外循环总共运行
n次 - 内循环将在1到
n次之间运行，具体取决于i当时的情况。 但是你知道平均来说这将是(n+1)/2次。 - 因此
count = n(n+1)/2)，即O(n^2)
算术系列
更新：根据要求 – 为什么内循环是(n+1)/2 ：
外循环将在1和n之间递增i。 因此，在外部循环的每次迭代中，内部循环将比以前“循环”一次。
因此内循环将迭代这么多次：
- 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时可视化，然后将其折叠成两半。）
我也强烈推荐阅读这个关于卡尔弗里德里希高斯的着名故事，所以你将永远记得如何总结算术系列=）
1
1 + 2 = 3
1 + 2 + 3 = 6
1 + 2 + 3 + 4 = 10
1 + 2 + 3 + 4 + 5 = 15
看到这种模式只有我吗？ 🙂
干得好：
count = n *（n + 1）/ 2