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

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


当前回答

将算法分解成你知道的大O符号,并通过大O运算符组合。这是我知道的唯一办法。

欲了解更多信息,请查看有关该主题的维基百科页面。

其他回答

看到这里的答案,我想我们可以得出这样的结论:我们大多数人确实通过观察它和使用常识来近似算法的顺序,而不是像我们在大学里认为的那样用主方法来计算它。 说了这么多,我必须补充一点,即使教授也鼓励我们(后来)实际思考,而不是仅仅计算。

我还想补充一下如何对递归函数进行处理:

假设我们有这样一个函数(scheme code):

(define (fac n)
    (if (= n 0)
        1
            (* n (fac (- n 1)))))

递归地计算给定数字的阶乘。

第一步是尝试并确定函数体的性能特征,只是在这种情况下,在函数体中没有做任何特殊的事情,只是一个乘法(或返回值1)。

所以主体的性能是:O(1)(常数)。

接下来尝试确定递归调用的数量。在这种情况下,我们有n-1个递归调用。

所以递归调用的性能是:O(n-1)(阶为n,因为我们抛弃了无关紧要的部分)。

然后把这两个放在一起,你就得到了整个递归函数的性能:

1 * (n-1) = O(n)


Peter, to answer your raised issues; the method I describe here actually handles this quite well. But keep in mind that this is still an approximation and not a full mathematically correct answer. The method described here is also one of the methods we were taught at university, and if I remember correctly was used for far more advanced algorithms than the factorial I used in this example. Of course it all depends on how well you can estimate the running time of the body of the function and the number of recursive calls, but that is just as true for the other methods.

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

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

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

对于第一种情况,内部循环执行了n-i次,因此执行的总次数是i从0到n-1(因为小于,而不是小于或等于)的和。你得到最后n * (n + 1) / 2,所以O (n²/ 2)= O (n²)。

对于第二个循环,i在0到n之间。然后,当j严格大于n时执行内循环,这是不可能的。

我不知道如何通过编程来解决这个问题,但人们做的第一件事是我们对算法的特定模式进行抽样,比如4n²+ 2n + 1我们有两个规则:

如果我们有一个项的和,增长率最大的项被保留,其他项被省略。 如果我们有几个因数的乘积,常数因数就省略了。

如果我们化简f(x),其中f(x)是所做操作数量的公式,(上文解释的4n²+ 2n + 1),我们得到大O值[在这种情况下是O(n²)]。但这必须考虑到程序中的拉格朗日插值,这可能很难实现。如果真正的大O值是O(2^n)我们可能有O(x^n)这样的东西,那么这个算法可能是不可编程的。但如果有人证明我错了,给我代码. . . .

熟悉我使用的算法/数据结构和/或快速分析迭代嵌套。难点在于,当您调用一个库函数时,可能会多次调用—您常常不确定是否在不必要的时候调用了函数,或者它们正在使用什么实现。也许库函数应该有一个复杂度/效率度量,无论是大O还是其他度量,都可以在文档或智能感知中得到。