一尘不染

大哦记法

algorithm

只需要对真正快速的事情进行确认。如果一个算法需要n(n-1)/2测试才能运行,那是很大的哦O(n^2)


阅读 255

收藏
2020-07-28

共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)中

2020-07-28