algorithm - 算法时间复杂度

Question

我正在研究一种算法，该算法在最坏的情况下会执行许多这样的操作：

N + (N -1) + (N - 2) + (N - 3) + ... + [N - (N -1)] + (N -N)

在大 O 符号分析中，这个算法是线性的、二次的还是其他的？

非常感谢你。

score 6 · Accepted Answer

6

这是数学。你的总和正好等于N*(N+1)/2

于 2013-02-07T10:23:30.317 回答

score 2 · Accepted Answer

2

你的公式是“小高斯”。它等于n(n+1)/2。

高斯技巧方程

这是 O( (n*n + n)/2 ) = O(n ² )

于 2013-02-07T10:33:02.653 回答

2 回答 2