Warm tip: This article is reproduced from serverfault.com, please click

performance-大O,将一系列n个数相加的复杂度是多少?

(performance - Big O, what is the complexity of summing a series of n numbers?)

发布于 2012-02-12 21:34:21

我一直认为:

1 + 2 + 3 + ... + n 是O(n),将两个n×n矩阵相加就是O(n ^ 2)。

但是今天我从一本教科书中读到,“通过前n个整数之和的公式,这是n(n + 1)/ 2”,然后是:(1/2)n ^ 2 +(1/2) n,因此为O(n ^ 2)。

我在这里想念什么?

Questioner
user1032613
Viewed
0
svick 2012-02-13 05:47:22

大O表示法可用于确定增长率的任何功能。

在这种情况下,这本书似乎不是在谈论计算价值的时间复杂性,而是价值本身。n(n+1)/2O(n^2)