在 Coursera 上的普林斯顿教程中,讲师解释了遇到的常见增长顺序函数。他说,线性和线性算术运行时间是“我们努力的目标”,他的推理是,随着输入大小的增加,运行时间也会增加。我认为这是他犯了错误的地方,因为我之前听过他提到线性增长顺序对于高效算法来说并不令人满意。
在讲话时,他还展示了一张绘制不同运行时间的图表 - 恒定和对数运行时间看起来更有效。那么这是一个错误还是事实如此?
如果认为 O(n) 和 O(n log n) 函数比 O(1) 和 O(log n) 函数具有更好的复杂性,那么这是一个错误。当以大 O 表示法查看复杂性的典型案例时:
O(1)
请注意,这并不一定意味着它们在性能方面总是更好 - 我们可能有一个 O(1) 函数,尽管它的复杂性不受元素计数的影响,但它需要很长时间才能执行。这样的函数在大 O 表示法中看起来比 O(log n) 函数更好,但实际上在实践中可能表现更差。
一般来说:复杂度较低的函数(以大 O 表示法)将优于复杂度较高的函数(以大 O 表示法)当 n 足够高时.
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)