大O符号比例因子问题
我有2个算法来做一些事情（例如搜索一个列表），一个具有线性复杂度，另一个具有日志复杂度（O（log n））。如果我比较100和1000单位的操作，那么我说线性算法是否具有比例因子X10？
我如何表达日志算法比例因子？ 例如100个项目需要2秒，1000个项目需要3秒。 1000的对数是3，100的对数是2.那么什么是比例因子？ X1.5？
我可以看到时间的增长是对数的。 或者你只是说缩放因子是对数？ 但是，如果比较100到1000个项目，你会计算什么？
我会把它作为“它以线性/二次/三次/对数/指数形式进行缩放”，我根本不会参考确切的缩放因子。 大O不是特定的时间，它是一种将算法放入特定类的方法，即。 线性类，对数类等
重点不在于对确切的运行时做出假设（这受到许多细节的影响，完全取决于算法运行的机器），而是要能够用相对术语来说明，所以可以说O（ n 2）算法将比O（n），O（log n）一目了然。
您的问题预先假定“比例因子”对于除线性以外的任何复杂性顺序都是有意义的，但情况根本不是这样。 但即使是线性的，这也是毫无意义的。 请看，仅仅因为算法是O(n)并不意味着尺寸为2x的输入将会像尺寸x的输入那样“长”两倍。
你的问题也预示着普遍的误解，即复杂性的顺序可以转化为时间。 不是这样。 对于算法的渐近分析而言，复杂度的顺序非常有用，而不是用于测量完成时间的特定输入大小。
一般来说，由于大O复杂度会忽略对计算比例因子至关重要的系数和常数，因此无法从大O复杂度计算数值比例因子。
如果算法A具有(1/1000) * n + 100的实际复杂度，而算法B具有100*log(n) + 1的实际复杂度，则算法A是O（n），而算法B是O（log（n ））。 然而，当你从n从100增加到n时，A从100.1的成本降低到101，而B从201的成本降低到301.算法A的实际运行时间仅增加1％，而算法B的实际运行时间增加了50％。
大O符号旨在告诉你如何随着n变成无穷大而变大。 当您查看实际的非无限范围时，具有更好Big O符号的算法完全有可能比具有更糟Big O符号的算法更慢并且效率更低。 对于足够大的n，具有更好的Big O符号的算法最终将获胜。 但是，不能保证交叉点实际上在任何特定目的的预期范围内。
链接地址: http://www.djcxy.com/p/6811.html上一篇: Question on Big O notation scaling factor
下一篇: O time complexity