软件设计：大O

作者:StringArray更新于： 2020-04-11 21:05:35

　　大O符号(BigOnotation)是用于描述函数渐进行为的数学符号。更确切地说，它是用另一个(通常更简单的)函数来描述一个函数数量级的渐近上界。在数学中，它一般用来刻画被截断的无穷级数尤其是渐近级数的剩余项;在计算机科学中，它在分析算法复杂性的方面非常有用。

　　表示时间的大O符号，是用来描述算法效率的语言和度量单位。不彻底理解这个概念，不仅会影响你做出清晰的判断，还会让你无法评价算法的优劣。

　　1常量不算在运算时间里。

　　例如某个O(2N)的算法实际上是O(N)。特定输入中，O(N)很有可能会比O(1)代码还要快。大O仅仅描述了增长的趋势。

　　2丢弃不重要的项

　　应该舍弃无关紧要的项。比如O(N2+N)变成O(N2)、O(N+logN)变成O(N)、O(5*2^N+1000N^100)变成O(2^N)等。

　　3logN运行时间

　　元素的个数每次减半，它的运行时间很可能是O(logN)。

　　以二分查找为例。假设一个排序数组长度为N，目标值为x。首先比较x与中值，如果x等于中值直接返回，如果小于中值，搜索数组的左边，如果大于中值，搜索数组的右边。

　　开始时有N个元素的排序数组要搜索，经过一次搜索之后，还剩下N/2个元素，再一次，剩下N/4个元素，直到找到目标值或者待搜索元素个数为1时才停止搜索。

　　同理，在平衡二叉搜索树中查找一个元素也是O(logN)，每次比较，非左即右。

　　4递归的运行时间

　　当一个多次调用自己的递归函数出现时，它的运行时间往往是O(分支数^数的深度)，分支数即每次调用自己的次数。

　　例如：

　　intf(intn){

　　if(n<=1){

　　return1;

　　}

　　returnf(n-1)+f(n-1);

　　}

　　运行时间是O(2^N)。

　　这个例子的空间复杂度为O(N)，尽管树节点总数为O(2^N)，但同一时刻只有O(N)个节点存在。

　　再例如：

　　把平衡二叉搜索树上所有节点的值相加，运行时间是多少？

　　分支树是2，深度大概是logN，所以为O(2^logN)=O(N),运行时间是O(N)。

　　大O符号是由德国数论学家保罗·巴赫曼(PaulBachmann)在其1892年的著作《解析数论》(AnalytischeZahlentheorie)首先引入的。而这个记号则是在另一位德国数论学家艾德蒙·朗道(EdmundLandau)的著作中才推广的，因此它有时又称为朗道符号(Landausymbol)。代表"orderof..."(……阶)的大O，最初是一个大写的希腊字母'Ο'(Omicron)，现今用的是英文大写字母'O'，但从来不是阿拉伯数字'0'。