算法（一）——时间复杂度及常用排序算法时间复杂度

谁践踏了优雅 2021-12-10 11:19 398阅读 0赞

### 文章目录 ###

*  算法效率度量
 *  时间复杂度
 *  master公式
 *  常用排序算法及其时间复杂度
 *   *  冒泡排序(bubblesort)：$O(N^\{2\})$
     *  选择排序：$O(N^\{2\})$
     *  插入排序：$O(N^\{2\})$
     *  归并排序：$O(Nlog\{N\})$
     *  总结

# 算法效率度量 #

1.时间复杂度O(n)  
原则：

1.  常数1代替所有加法中的常数
2.  只保留最高阶数项(且不要前面的系数)
3.  O(1)<O(log n)<O(n)<O(n logn)<O(n^2)

2.空间复杂度  
常用空间换时间

# 时间复杂度 #

时间复杂度：算法性能指标（本质常数时间操作的个数）；先看指标再看系数；先看高阶项再看低阶项  
常数时间操作：例如位操作、算术运算等。

# master公式 #

T ( N ) = a T ( N / b ) + O ( N d ) T(N)=aT(N/b)+O(N^\{d\}) T(N)=aT(N/b)\+O(Nd)  
其中a表示子过程发生次数，b表示子过程样本量，  
 l o g b a > d → log^\{a\}\_\{b\}>d \\rightarrow logba>d→复杂度为 O ( N l o g b a ) O(N^\{log^\{a\}\_\{b\}\}) O(Nlogba)  
 l o g b a = d → log^\{a\}\_\{b\}=d \\rightarrow logba=d→复杂度为 O ( N d l o g N ) O(N^\{dlog^\{N\}\}) O(NdlogN)  
 l o g b a > d → log^\{a\}\_\{b\}>d \\rightarrow logba>d→复杂度为 O ( N d ) O(N^\{d\}) O(Nd)

# 常用排序算法及其时间复杂度 #

## 冒泡排序(bubblesort)： O ( N 2 ) O(N^\{2\}) O(N2) ##

## 选择排序： O ( N 2 ) O(N^\{2\}) O(N2) ##

## 插入排序： O ( N 2 ) O(N^\{2\}) O(N2) ##

时间复杂度与数据状况有关，最好 O ( N ) O(N) O(N)最差 O ( N 2 ) O(N^\{2\}) O(N2)。但算法性能一律按最差考虑，即插入排序时间复杂度为 O ( N 2 ) O(N^\{2\}) O(N2)

## 归并排序： O ( N l o g N ) O(Nlog\{N\}) O(NlogN) ##

分治思想

## 总结 ##

<table> 
 <tbody> 
  <tr> 
   <th colspan="2">常用排序算法</th> 
   <th colspan="3">时间复杂度</th> 
   <th>空间复杂度</th> 
   <th>稳定性</th> 
  </tr> 
  <tr> 
   <td>平均情况</td> 
   <td>最好情况</td> 
   <td>最坏情况</td> 
   <td>辅助存储</td> 
  </tr> 
  <tr> 
   <td>交换排序</td> 
   <td>冒泡排序</td> 
   <td> O(n*n)</td> 
   <td> O(n)</td> 
   <td> O(n*n)</td> 
   <td> O(1)</td> 
   <td> 稳定</td> 
  </tr> 
  <tr> 
   <td>快速排序</td> 
   <td> O(n*logn)</td> 
   <td> O(n*logn)</td> 
   <td> O(n*n)</td> 
   <td> O(n*logn)</td> 
   <td> 不稳定</td> 
  </tr> 
  <tr> 
   <td>插入排序</td> 
   <td>直接插入</td> 
   <td> O(n*n)</td> 
   <td> O(n)</td> 
   <td> O(n*n)</td> 
   <td> O(1)</td> 
   <td> 稳定</td> 
  </tr> 
  <tr> 
   <td>shell排序</td> 
   <td> O(n*n)</td> 
   <td> O(n)</td> 
   <td> O(n*n)</td> 
   <td> O(1)</td> 
   <td> 不稳定</td> 
  </tr> 
  <tr> 
   <td>选择排序</td> 
   <td>直接选择</td> 
   <td> O(n*n)</td> 
   <td> O(n*n)</td> 
   <td> O(n*n)</td> 
   <td> O(1)</td> 
   <td> 不稳定</td> 
  </tr> 
  <tr> 
   <td>堆排序</td> 
   <td> O(n*logn)</td> 
   <td> O(n*logn)</td> 
   <td> O(n*logn)</td> 
   <td> O(1)</td> 
   <td> 不稳定</td> 
  </tr> 
  <tr> 
   <td colspan="2">归并排序</td> 
   <td> O(n*logn)</td> 
   <td> O(n*logn)</td> 
   <td> O(n*logn)</td> 
   <td> O(n)</td> 
   <td> 稳定</td> 
  </tr> 
 </tbody> 
</table>