大多数拥有计算机科学学位的人肯定知道大O代表什么。 它帮助我们衡量一个算法的可扩展性。
但我很好奇,你是如何计算或近似你的算法的复杂性的?
大多数拥有计算机科学学位的人肯定知道大O代表什么。 它帮助我们衡量一个算法的可扩展性。
但我很好奇,你是如何计算或近似你的算法的复杂性的?
当前回答
我认为,一般来说用处不大,但为了完整起见,还有一个Big Omega Ω,它定义了算法复杂度的下界,还有一个Big Theta Θ,它同时定义了上界和下界。
其他回答
熟悉我使用的算法/数据结构和/或快速分析迭代嵌套。难点在于,当您调用一个库函数时,可能会多次调用—您常常不确定是否在不必要的时候调用了函数,或者它们正在使用什么实现。也许库函数应该有一个复杂度/效率度量,无论是大O还是其他度量,都可以在文档或智能感知中得到。
如果你的成本是一个多项式,只保留最高次项,而不保留它的乘数。例如:
(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!)
基本上90%的情况下都是分析循环。你有单、双、三重嵌套循环吗?你有O(n) O(n²)O(n³)的运行时间。
很少(除非你正在编写一个具有广泛基库的平台(例如,.NET BCL或c++的STL),你会遇到比查看循环(for语句,while, goto等…)更困难的事情。
我不知道如何通过编程来解决这个问题,但人们做的第一件事是我们对算法的特定模式进行抽样,比如4n²+ 2n + 1我们有两个规则:
如果我们有一个项的和,增长率最大的项被保留,其他项被省略。 如果我们有几个因数的乘积,常数因数就省略了。
如果我们化简f(x),其中f(x)是所做操作数量的公式,(上文解释的4n²+ 2n + 1),我们得到大O值[在这种情况下是O(n²)]。但这必须考虑到程序中的拉格朗日插值,这可能很难实现。如果真正的大O值是O(2^n)我们可能有O(x^n)这样的东西,那么这个算法可能是不可编程的。但如果有人证明我错了,给我代码. . . .
对于代码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)