大多数拥有计算机科学学位的人肯定知道大O代表什么。 它帮助我们衡量一个算法的可扩展性。
但我很好奇,你是如何计算或近似你的算法的复杂性的?
大多数拥有计算机科学学位的人肯定知道大O代表什么。 它帮助我们衡量一个算法的可扩展性。
但我很好奇,你是如何计算或近似你的算法的复杂性的?
当前回答
我想从另一个角度来解释Big-O。
Big-O只是用来比较程序的复杂性,也就是当输入增加时它们的增长速度有多快,而不是花在执行操作上的确切时间。
恕我直言,在大o公式中,你最好不要使用更复杂的方程(你可以坚持使用下图中的方程)。然而,你仍然可以使用其他更精确的公式(如3^n, n^3,…),但有时会误导!所以还是尽量简单为好。
我想再次强调,这里我们不想得到一个精确的算法公式。我们只想展示当输入增加时它是如何增长的并在这方面与其他算法进行比较。否则,您最好使用不同的方法,如基准测试。
其他回答
经常被忽视的是算法的预期行为。它不会改变你的算法的大o,但它确实与“过早优化.. ..”的声明有关
你的算法的预期行为是——非常简单——你期望你的算法在你最有可能看到的数据上工作的速度有多快。
例如,如果你在一个列表中搜索一个值,它是O(n),但如果你知道你看到的大多数列表都有你的值在前面,你的算法的典型行为会更快。
为了真正确定它,你需要能够描述你的“输入空间”的概率分布(如果你需要对一个列表排序,这个列表已经被排序的频率是多少?有多少次是完全相反的?多长时间进行一次排序?)这并不总是可行的,但有时你知道。
至于“如何计算”大O,这是计算复杂性理论的一部分。对于一些(许多)特殊的情况,您可能会使用一些简单的启发式方法(例如为嵌套循环乘以循环计数),特别是当您想要的只是任何上限估计时,并且您不介意它是否过于悲观——我猜这可能就是您的问题的内容。
如果你真的想回答任何算法的问题你能做的最好的就是应用这个理论。除了简单的“最坏情况”分析,我发现平摊分析在实践中非常有用。
我认为,一般来说用处不大,但为了完整起见,还有一个Big Omega Ω,它定义了算法复杂度的下界,还有一个Big Theta Θ,它同时定义了上界和下界。
如果你的成本是一个多项式,只保留最高次项,而不保留它的乘数。例如:
(O (n / 2) + 1) * (n / 2)) = O (n2/4 = O (n / 2) + n2/4) = O (n2)
注意,这对无穷级数不成立。对于一般情况,没有单一的方法,但对于一些常见情况,适用以下不等式:
O(log N) < O(N) < O(N log N) < O(N2) < O(Nk) < O(en) < O(n!)
不要忘记考虑空间的复杂性,如果内存资源有限,这也是一个值得关注的问题。例如,你可能听到有人想要一个常数空间算法,这基本上是说算法所占用的空间量不依赖于代码中的任何因素。
有时,复杂性可能来自于某个东西被调用了多少次,循环执行的频率,内存分配的频率,等等,这是回答这个问题的另一部分。
最后,大O可以用于最坏情况、最佳情况和摊销情况,其中通常用最坏情况来描述算法可能有多糟糕。