开发高效算法

Bertha 。 2022-05-20 10:42 266阅读 0赞

*   *  1. 引言
     *  2. 使用大O符号来衡量算法效率
     *  3. 分析算法的时间复杂度
        
         *  3.1 二分查找算法
         *  3.2 常用的递推关系
         *  3.3 比较常用的增长函数
     *  4. 总结

## 1. 引言 ##

算法设计是为了解决某个问题开发一个数学流程。算法分析是预测一个算法的性能。

## 2. 使用大O符号来衡量算法效率 ##

大O符号标记可以基于输入的大小得到一种衡量算法时间复杂度的函数。**可以忽略函数中的倍乘常量和非主导项**。其本质是比较算法之间的增长率。对于一个线性查找的算法，其时间复杂度表示方法为O(n)，读作“n阶”。  
\- 最佳情况输入：导致最短执行时间的输入  
\- 最差情况输入：导致最长执行时间的输入，可以确定算法不会比最差情况还慢

分析通常针对最坏情况进行。大O符号允许忽略非主导部分（例如，表达式n-1中的-1），并强调重要部分（例如，表达式n-1中的n），因此，该算法的复杂度为O(n)。如果执行时间与输入规模无关就称该算法耗费了常量时间，用符号O(1)表示。

1\+2\+3\+...\+(*n*−2)\+(*n*−1)=*n*(*n*−1)2=*O*(*n*2)  1 + 2 + 3 + . . . + ( n − 2 ) + ( n − 1 ) = n ( n − 1 ) 2 = O ( n 2 )

*a*0\+*a*1\+*a*2\+...\+*a**n*=*a**n*\+1−1*a*−1=*O*(*a**n*)  a 0 + a 1 + a 2 + . . . + a n = a n + 1 − 1 a − 1 = O ( a n )

备注：时间复杂度是使用大O标记对运行时间进行测量。类似的，也可以使用大O标记对空间复杂度进行测量。

## 3. 分析算法的时间复杂度 ##

### 3.1 二分查找算法 ###

每次迭代包含固定次数的操作，次数由c来表示，不失一般性，假定n是2的幂,采用递推公式求解。

*T*(*n*)=*T*(*n*2)\+*c*=*T*(*n*22)\+2\+2=*T*(*n*2*k*)\+*k**c*  T ( n ) = T ( n 2 ) + c = T ( n 2 2 ) + 2 + 2 = T ( n 2 k ) + k c

当递推到最后一个元素时，前部分为T(1)

*k*=*l**o**g**n*  k = l o g n

*T*(*n*)=*T*(1)\+*c*log*n*=*O*(log*n*)  T ( n ) = T ( 1 ) + c log ⁡ n = O ( log ⁡ n )

### 3.2 常用的递推关系 ###

递推关系对于分析算法时间复杂度非常有用，常用的递推关系如下表格,其时间复杂度的递推方法与3.1方法相同

<table> 
 <thead> 
 <tr> 
 <th>地推关系</th> 
 <th>结果</th> 
 <th>示例</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td> T(n)=T(n/2)+O(1) T ( n ) = T ( n / 2 ) + O ( 1 ) </td> 
 <td> T(n)=O(logn) T ( n ) = O ( log ⁡ n ) </td> 
 <td>二分查找，欧几里得求解最大公约数</td> 
 </tr> 
 <tr> 
 <td> T(n)=T(n−1)+O(1) T ( n ) = T ( n − 1 ) + O ( 1 ) </td> 
 <td> T(n)=O(n) T ( n ) = O ( n ) </td> 
 <td>线性查找</td> 
 </tr> 
 <tr> 
 <td> T(n)=2T(n/2)+O(1) T ( n ) = 2 T ( n / 2 ) + O ( 1 ) </td> 
 <td> T(n)=O(n) T ( n ) = O ( n ) </td> 
 <td></td> 
 </tr> 
 <tr> 
 <td> T(n)=2T(n/2)+O(n) T ( n ) = 2 T ( n / 2 ) + O ( n ) </td> 
 <td> T(n)=O(nlogn) T ( n ) = O ( n log ⁡ n ) </td> 
 <td>归并排序</td> 
 </tr> 
 <tr> 
 <td> T(n)=T(n−1)+O(n) T ( n ) = T ( n − 1 ) + O ( n ) </td> 
 <td> T(n)=O(n2) T ( n ) = O ( n 2 ) </td> 
 <td>选择排序</td> 
 </tr> 
 <tr> 
 <td> T(n)=2T(n−1)+O(1) T ( n ) = 2 T ( n − 1 ) + O ( 1 ) </td> 
 <td> T(n)=O(2n) T ( n ) = O ( 2 n ) </td> 
 <td>汉诺塔</td> 
 </tr> 
 <tr> 
 <td> T(n)=T(n−1)+T(n−2)+O(1) T ( n ) = T ( n − 1 ) + T ( n − 2 ) + O ( 1 ) </td> 
 <td> T(n)=O(2n) T ( n ) = O ( 2 n ) </td> 
 <td>递归的斐波那契算法</td> 
 </tr> 
 </tbody> 
</table>

### 3.3 比较常用的增长函数 ###

![函数增长趋势][095807529.jpg]

函数增长趋势

## 4. 总结 ##

1.  大O标记是分析算法性能的理论方法。他估计算法的执行时间随着输入规模的增加会有多快的增长。因此，可以通过检查两个算法的增长率来比较他们。
2.  最佳情况和最差清空都不具有代表性，但是最差情况分析非常有用。你可以确保算法永远不会比最差情况还慢

参考资料：《Java语言程序设计（进阶篇）》

[095807529.jpg]: /images/20220520/3400178dc0f84249af189ca296f1f6f3.png