java - 作为 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 到 n 次，具体取决于当时的 i 是什么。但是您知道这平均会运行 (n+1)/2 次。
• 因此 count = n(n+1)/2)，也就是 O(n^2)

参见 arithmetic series

更新:根据要求 - 为什么内循环是 (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，然后将它对折。)

我也强烈建议阅读此 famous story about Karl Friedrich Gauss所以你会永远记得如何对算术级数求和 =)