大O符号表示法

Question

只需要快速确认一件事情。 如果一个算法需要 n(n-1)/2 次测试才能运行，那么大O表示法是否为 O(n^2)？

- Jay

Answer 1

n(n-1)/2可以展开为(n^2 -n) / 2，即(n^2/2) - (n/2)

(n^2/2)和(n/2)是两个函数组成部分，其中n^2/2占主导地位。 因此，我们可以忽略- (n/2)部分。

从n^2/2中，您可以在渐近符号分析中安全地删除/2部分。

这简化为 n^2

因此，是的，它是O(n^2)。

- user237076

Answer 2

是的，那是正确的。

n(n-1)/2 展开为 n^2/2 - n/2：

线性项 n/2 被消除了，因为它是低阶的。这留下了n^2/2。常数被吸收到大O符号中，留下了n^2。

- Mysticial

---

@Jay，如果你认为答案解决了你的问题，那么请接受它。 - user237076

Answer 3

是的：

n(n-1)/2 = (n2-n)/2 = O(n^2)

- Luchian Grigore

Answer 4

是的，它是正确的。 n（n-1）/2 是 （n^2-n）/2，显然对于所有 n>=1，只要您选择至少为1的 c ，它就明显小于c*n^2。

- sepp2k