java - 确定增加变量计数的语句执行频率为 n 的函数

Question

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

score 4 · Accepted Answer

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

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

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

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

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

由于我们将它们配对，因此我们有 n/2 对这样的配对：

（想象一下，当你在一条长纸条上写 1 + 2 + 3 + ... + n 时，你把它对折。）

我也强烈推荐阅读这个关于卡尔弗里德里希高斯的著名故事，这样你就会永远记得如何对算术级数求和 =)

score 1 · Accepted Answer

1

1+2 = 3

1+2+3 = 6

1+2+3+4 = 10

1+2+3+4+5 = 15

只有我能看到模式吗？:-)

于 2012-11-20T22:48:03.023 回答

score 1 · Accepted Answer

1

干得好：

计数 = n * (n + 1) / 2

于 2012-11-20T22:52:46.717 回答

3 回答 3