好了，所以我是新来分析算法和倒很AP preciate可以在如何去这个共享的任何有用的提示。我想，以确定有多少次计数加为n的函数。我已经跑在它的IDE和值1-7输出为1,3,6,10,15,21,28。我只是不知道该如何写这为n的函数？谢谢。 循环如下：

 的for（int i = 1; I＆LT; = N;我++）{

    对于（INT J = 1; J＆LT; = I，J ++）{

         算上++;
    }
}
 

解决方案

这种类型的活动的目的是教如何分析你的机器上运行它的故纸代替。但是，让我们来看看模式：

在外环将运行总计 N 次 在内环将1之间运行ñ时间取决于什么我在当时。但是你知道，平均而言这将运行（N + 1）/ 2 倍。 因此数= N（N + 1）/ 2），这是为O（n ^ 2）

请参阅算术系列

更新：作为请求 - 为什么内环是（N + 1）/ 2 ：

外环将增量I 1和N之间。等外部循环的每次迭代中，内环将循环1以上的确要比previously

这样的内循环将迭代该次数：

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在一张长条形的，而你对折。）

我也强烈建议你阅读这篇著名的故事，关于卡尔·弗里德里希·高斯所以你'会永远记住如何总结等差数列=）

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:

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)

See arithmetic series

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

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 with 1: (n + 1) = n + 1 n-1 with 2: (n - 1) + 2 = n + 1 n-2 with 3: (n - 2) + 3 = n + 1 ...

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

So the sum of 1 + 2 + ... + n is ( (n+1) * (n/2) ). So the average is ( (n+1) * (n/2) ) / n = (n+1)/2

(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 =)