大多数拥有计算机科学学位的人肯定知道大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还是其他度量,都可以在文档或智能感知中得到。
将算法分解成你知道的大O符号,并通过大O运算符组合。这是我知道的唯一办法。
欲了解更多信息,请查看有关该主题的维基百科页面。
基本上90%的情况下都是分析循环。你有单、双、三重嵌套循环吗?你有O(n) O(n²)O(n³)的运行时间。
很少(除非你正在编写一个具有广泛基库的平台(例如,.NET BCL或c++的STL),你会遇到比查看循环(for语句,while, goto等…)更困难的事情。
好问题!
免责声明:这个答案包含虚假陈述,见下面的评论。
如果您正在使用大O,那么您正在谈论的是最坏的情况(后面将详细介绍它的含义)。此外,在平均情况下有大写的theta,在最佳情况下有大的omega。
你可以在这个网站上找到大O的正式定义:https://xlinux.nist.gov/dads/HTML/bigOnotation.html
f(n) = O(g(n))表示存在正常数c和k,使得当n≥k时0≤f(n)≤cg(n)。对于函数f, c和k的值必须是固定的,且不依赖于n。
好的,那么我们所说的"最佳情况"和"最坏情况"是什么意思呢?
这一点可以通过例子得到最清楚的说明。例如,如果我们使用线性搜索在一个排序数组中查找一个数字,那么最坏的情况是我们决定搜索数组的最后一个元素,因为这将花费与数组中有多少项一样多的步骤。最好的情况是当我们搜索第一个元素时,因为我们将在第一次检查之后完成。
The point of all these adjective-case complexities is that we're looking for a way to graph the amount of time a hypothetical program runs to completion in terms of the size of particular variables. However for many algorithms you can argue that there is not a single time for a particular size of input. Notice that this contradicts with the fundamental requirement of a function, any input should have no more than one output. So we come up with multiple functions to describe an algorithm's complexity. Now, even though searching an array of size n may take varying amounts of time depending on what you're looking for in the array and depending proportionally to n, we can create an informative description of the algorithm using best-case, average-case, and worst-case classes.
抱歉,这是如此糟糕的写作和缺乏太多的技术信息。但希望这能让时间复杂度类更容易理解。一旦你熟悉了这些,你就可以很简单地解析你的程序,寻找像for-loops这样依赖于数组大小的东西,并根据你的数据结构推理什么样的输入会导致简单的情况,什么样的输入会导致最坏的情况。
看到这里的答案,我想我们可以得出这样的结论:我们大多数人确实通过观察它和使用常识来近似算法的顺序,而不是像我们在大学里认为的那样用主方法来计算它。 说了这么多,我必须补充一点,即使教授也鼓励我们(后来)实际思考,而不是仅仅计算。
我还想补充一下如何对递归函数进行处理:
假设我们有这样一个函数(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.