令人困惑的一点是为什么你可能认为是O(2n),对列表中的每个项目执行两次操作的东西,以及你可能认为是O(n)的其他东西实际上都被认为是O(n)
这样做的原因是,当你开始使用庞大的数据集时,当你考虑如何与O(n ^ 2)或O(log)相比时,O(2n)和O(n)之间的差异并不是真正的巨大差异N).考虑一下您是否有3种不同的搜索算法来搜索数据集.数据集包含一百万个项目.每个算法将采取的操作数:
O(2n)= 2,000,000
O(n)= 1,000,000
O(n ^ 2)= 1,000,000,000,000
O(2n)只是O(n)的2倍,但O(n ^ 2)慢了一百万倍.这是一个令人难以置信的巨大差异! 所以Big O表示法实际上是处理算法如何"缩放",或者换句话说,当你考虑越来越大的数据集时,它的表现如何.
AO(n ^ 2)算法对于非常小的数据集表现良好,但是对于较大的数据集,其性能会迅速降低.O(2n)和O(n)将逐渐均匀地降级,这更接近于用户在处理更多数据时所期望的.
出于这个原因,人们不会谈论O(2n),他们只是谈论O(n),因为两者都代表线性时间(线性的,因为当你添加数据时,操作数量会逐渐增加和逐渐增加).
一开始认为某人执行速度慢两倍的算法仍被认为是O(n),但大O符号不是相对速度的衡量标准,这可能令人沮丧.Big O表示法衡量算法如何根据其处理的数据量进行扩展.