大多数拥有计算机科学学位的人肯定知道大O代表什么。 它帮助我们衡量一个算法的可扩展性。

但我很好奇,你是如何计算或近似你的算法的复杂性的?


当前回答

不要忘记考虑空间的复杂性,如果内存资源有限,这也是一个值得关注的问题。例如,你可能听到有人想要一个常数空间算法,这基本上是说算法所占用的空间量不依赖于代码中的任何因素。

有时,复杂性可能来自于某个东西被调用了多少次,循环执行的频率,内存分配的频率,等等,这是回答这个问题的另一部分。

最后,大O可以用于最坏情况、最佳情况和摊销情况,其中通常用最坏情况来描述算法可能有多糟糕。

其他回答

至于“如何计算”大O,这是计算复杂性理论的一部分。对于一些(许多)特殊的情况,您可能会使用一些简单的启发式方法(例如为嵌套循环乘以循环计数),特别是当您想要的只是任何上限估计时,并且您不介意它是否过于悲观——我猜这可能就是您的问题的内容。

如果你真的想回答任何算法的问题你能做的最好的就是应用这个理论。除了简单的“最坏情况”分析,我发现平摊分析在实践中非常有用。

基本上90%的情况下都是分析循环。你有单、双、三重嵌套循环吗?你有O(n) O(n²)O(n³)的运行时间。

很少(除非你正在编写一个具有广泛基库的平台(例如,.NET BCL或c++的STL),你会遇到比查看循环(for语句,while, goto等…)更困难的事情。

如果你的成本是一个多项式,只保留最高次项,而不保留它的乘数。例如:

(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还是其他度量,都可以在文档或智能感知中得到。

对于代码A,外层循环将执行n+1次,“1”时间表示检查i是否仍然满足要求的过程。内循环运行n次,n-2次....因此,0+2+..+(n-2)+n= (0+n)(n+1)/2= O(n²)。

对于代码B,虽然内部循环不会介入并执行foo(),但内部循环将执行n次,这取决于外部循环的执行时间,即O(n)