根据 n 的函数确定执行递增变量计数的语句的频率 [英] Determining as a function of n how often the statement incrementing the variable count is performed

问题描述

好的，所以我是分析算法的新手，非常感谢可以分享有关如何进行此操作的任何有用提示.我试图确定 count 作为 n 的函数增加了多少次.我在 ide 中运行它，对于值 1-7，输出为 1、3、6、10、15、21、28.我只是不确定如何将其写为 n 的函数?谢谢.循环如下:

Ok so I'm new to analyzing algorithms and would really appreciate any helpful tips that can be shared on how to go about this. I am trying to determine how many times count is incremented as a function of n. I have ran it in an ide and for values 1-7 the output is 1,3,6,10,15,21,28. Im just unsure how to write this as a function of n? Thanks. The loop is as follows:

for(int i = 1 ; i <= n ; i++){

    for (int j = 1 ; j <= i ; j++) {

         count++;
    }
}

推荐答案

这种类型的练习的目的是教你如何在纸上分析它而不是在机器上运行它.但是让我们看看模式:

The aim of this type of exercise is to teach how to you analyze it on paper instead of running it on a machine. But let's look at the pattern:

• 外循环将总共运行n次
• 内循环将运行 1 到 n 次，具体取决于当时 i 是什么.但是您知道这平均会运行 (n+1)/2 次.
• 因此count = n(n+1)/2)，即O(n^2)

• The outer loop will run a total of n times
• The inner loop will run between 1 to n times depend on what i is at the time. But you know that on average this will run (n+1)/2 times.
• Thus count = n(n+1)/2), which is O(n^2)

参见算术系列

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

Update: As requested - why the inner loop is (n+1)/2:

外循环将在 1 和 n 之间增加 i.因此，在外循环的每次迭代中，内循环将比之前多循环"一次.

The outer loop will increment i between 1 and n. So on each iteration of the outer loop, the inner loop will "loop" one more than than it did previously.

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

Thus the inner loop will iterate this number of times:

• 1 + 2 + 3 + ... + n

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

So we can do something clever and pair up :

• n 加 1:(n + 1) = n + 1
• n-1 加 2:(n - 1) + 2 = n + 1
• n-2 与 3:(n - 2) + 3 = n + 1
• ...

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

And since we paired these up, we have n/2 such pairs:

• 所以 1 + 2 + ... + n 的总和是 ( (n+1) * (n/2) ).
• 所以平均值是 ( (n+1) * (n/2) )/n = (n+1)/2

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

(Visualize it as you are writing 1 + 2 + 3 + ... + n on a long strip of paper, and you fold it in half.)

我还强烈建议您阅读这篇关于卡尔·弗里德里希·高斯的著名故事，以便您'我永远记得如何对等差数列求和 =)

I would also highly recommend reading this famous story about Karl Friedrich Gauss so you'll always remember how to sum arithmetic series =)

这篇关于根据 n 的函数确定执行递增变量计数的语句的频率的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！