这是在数据结构和算法课上，我遇到了这个疑问。网上和线下查了好几个资源，还是有疑问。我被要求计算出算法的运行时间，我正确地做到了 - O(n^3) 。但令我困惑的是这个问题 - 如果 n 从 90 到 900,000，算法的工作速度会慢多少？我的疑问是:
- 该算法的运行时间为 O(n^3) ，因此显然对于更大的输入来说需要更多的时间。 但我如何根据最坏情况的时间复杂度来比较不同输入的算法性能？
- 我们可以直接代入“n”的值并除以 big-O 以获得比率吗？
不对之处请指正!谢谢!
最佳答案
显然，你的想法是正确的!
随着算法的大小为 (n)，在最坏的情况下，如果大小增加，速度将与 n^3 成反比。
您的假设是正确的。您只需将 n=900,000 的值除以 n=90 即可得到结果。这个因子将是减速因子!
在这里，减速因子 = (900,000)^3/(90)^3 = 10^12 !
因此，slow factor=10^12 。你的程序将减慢 10^12 倍!!!如此剧烈的变化!或者换句话说，你的效率将下降 10^(-12) 倍!! !
根据建议的评论进行编辑:-
But how do I compare an algorithm's performance for different inputs based on just the worst case time complexity ?
正如这篇文章的评论员之一 G.Bach 所暗示的，你的问题背后的基本思想本身就是矛盾的!你应该谈论 Big-Theta Notation，不用Big-O来想通解! Big-O 是上界，而 Big-Theta 是紧界。当人们只担心可能发生的最坏情况时，big-O 就足够了；即它说“它不会比这更糟”。当然，边界越紧越好，但紧边界并不总是容易计算。
因此，在最坏的情况分析中，您的问题将以我们双方的回答方式得到回答。现在，人们使用 O 而不是 Ω 的一个狭义原因是放弃关于最坏或一般情况的免责声明。但是，为了进行更严格的分析，您必须同时检查 O 和 big-Omega 并提出问题。这个问题可以适本地找到不同大小的 n 的解决方案。我把它留给你去弄清楚。但是，如果你有任何疑问，请随时发表评论。
此外，您的运行时间与最坏情况分析没有直接关系，但在某种程度上是相关的，并且可以通过这种方式重新定义!
P.S.---> 我从 Big-oh vs big-theta 中获取了一些想法/陈述。 .所以，也要感谢作者!
希望对您有所帮助。如果有任何信息被浏览，请随时发表评论!
关于algorithm - 基于 Big O 的算法运行时间比较，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/24854859/