我试图在PC上运行程序的背景下理解Big O分析的一个特定方面.
假设我有一个性能为O(n + 2)的算法.如果n变得非常大,那么2变得微不足道.在这种情况下,非常清楚真正的性能是O(n).
但是,另一种算法的平均性能为O(n ^ 2/2).我看到这个例子的书说实际表现是O(n ^ 2).我不确定我明白为什么,我的意思是在这种情况下,2似乎并非完全无足轻重.所以我正在寻找书中一个很好的清晰解释.这本书以这种方式解释:
"考虑1/2意味着什么.检查每个值的实际时间高度依赖于代码转换的机器指令,然后取决于CPU执行指令的速度.因此1/2不会非常意思."
我的反应是......嗯??? 我完全不知道那句话是什么,或者更确切地说,这句话与他们的结论有什么关系.请允许有人为我拼出来.
谢谢你的帮助.
通常,一些答案提到给定的解决方案是线性的,或者另一个解决方案是二次的.
如何区分/识别什么是什么？
对于像我这样仍然不知道的人,有人可以解释这个,这是最简单的方法吗？