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

Question

好的，所以我是分析算法的新手，并且非常感谢可以共享的有用提示。我试图确定计数作为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++;
    }
}

Answer 1

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

• 外环将运行总计n次
• 内部循环将在1到2 n倍之间运行，具体取决于i当时的状态。但是您知道平均而言，这将运行(n+1)/2时间。
• 因此count = n(n+1)/2)，这是O(n^2)

见算术级数

更新： 根据要求-为什么内循环是(n+1)/2：

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

因此，内部html" target="_blank">循环将迭代此次数：

• 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）的著名故事，
以便您永远记住如何对算术级数求和=）