等差数列的复杂度是多少？

Question

我不太明白如何计算代码的复杂度。有人告诉我，我需要查看代码中对每个项目执行的操作数。因此，当我有一个循环遍历数组并基于算术级数的想法（我想计算从每个索引到数组末尾的总和）时，这意味着首先我传递 n 个单元格，第二次传递 n -1 个单元等等......为什么复杂性被认为是 O(N^2) 而不是 O(n)？

在我看来，n + n-1 +n-2 + n-c.. 是 xn -c ，换句话说就是 O(n)。那为什么我错了？

Answer 1

等差数列有闭式解，其计算效率为o(1)：即计算时间与元素个数无关

如果您要使用循环，那么它将是 o(n)，因为执行时间与元素数量呈线性关系。

Answer 2

As I see it, n + n-1 +n-2 + n-c.. is xn -c , In other words O(n). SO WHY am i wrong ?

其实不然。这个等差级数的和是n*(n-1)/2 = O(n^2)

P.S 我已经阅读了您的任务：您只需要使用之前的结果对数组进行一次循环，因此您可以用 O(n) 的复杂度来解决这个问题。

for i=1 to n 
 result[i] = a[i]+result[i-1]

Answer 3

您将平均值为 (n/2) 的 n 个数字相加，因为它们的范围是从 1 到 n。因此 n 次 (n/2) = n^2 / 2。我们不关心常数倍数，所以 O(n^2).

Answer 4

您的代码要执行的操作如下：-

traverse array from 1 to n
traverse array from 2 to n
... similarly after total n-1 iterations
traverse array's nth element

正如您所注意到的，单元格的数组遍历按 1 的顺序递减。

每次遍历都由循环引导，循环增加到 i 的值。整个代码包裹在 n.

的函数下

对数组的每个项目执行的操作数的具体想法是：-

for ( i = 1 to n )
for ( j = i to n )
traverse array[j] ;

因此，您的代码的复杂性 = O(n^2) 并且顺序显然在 AP 中，因为它形成了序列 n + (n-1) + ... + 1，公差为 1。

我希望清楚...

Answer 5

你哪里弄错了！一个等差级数的和是n^{2}的阶

要消除您对等差级数的疑虑，请访问此link：http://www.mathsisfun.com/algebra/sequences-sums-arithmetic.html

正如您所说，您很难找到任何代码的复杂性，您可以从这两个 link 中阅读：

http://discrete.gr/complexity/

http://www.cs.cmu.edu/~adamchik/15-121/lectures/Algorithmic%20Complexity/complexity.html

足以让你继续前进并帮助你理解如何找到大多数算法的复杂性。

Answer 6

时间复杂度为：1 + 2 + ... + n.

这等于n(n+1)/2。

例如，对于 n = 3：1 + 2 + 3 = 6 和 3(4)/2 = 12/2 = 6

n(n+1)/2 = (n^2 + n) / 2 即 O(n^2) 因为我们可以删除常数因子和低阶项。

等差数列的复杂度是多少？

What is the complexity of an arithmetic progression?

algorithm

math

time-complexity