大哦记谱法

Question

只需要快速确认一些事情.如果一个算法需要n(n-1)/2运行测试,那么大喔O(n^2)？

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)

Answer 2

对,那是正确的.

n(n-1)/2扩展为n^2/2 - n/2:

线性项n/2下降是因为它的次序较低.这离开了n^2/2.常数被吸收到大O中,留下n^2.