简说大O表示法

旧城等待， 2022-02-20 01:11 346阅读 0赞

**大O表示法：**  
算法的时间复杂度通常用大O符号表述，定义为T\[n\] = O(f(n))。称函数T(n)以f(n)为界或者称T(n)受限于f(n)。 如果一个问题的规模是n，解这一问题的某一算法所需要的时间为T(n)。T(n)称为这一算法的“时间复杂度”。当输入量n逐渐加大时，时间复杂度的极限情形称为算法的“渐近时间复杂度”。

**最坏时间复杂度：**  
算法的时间复杂度不仅与语句频度有关，还与问题规模及输入实例中各元素的取值有关。一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。这就保证了算法的运行时间不会比任何更长。

**求数量级：**  
即求对数值（log），默认底数为10，简单来说就是“一个数用标准科学计数法表示后，10的指数”。例如，5000=5x10 ³ (log5000=3） ，数量级为3。另外，一个未知数的数量级为其最接近的数量级，即最大可能的数量级。

**求极限的技巧：**  
要利用好1/n。当n趋于无穷大时，1/n趋向于0。

**一些常见的大O运行时间：**  
下面按由快到慢的顺序列出了常见的5种大O运行时间。  
1、O (log n )，也叫对数时间 ，这样的算法包括二分查找。  
2、O (n )，也叫线性时间 ，这样的算法包括简单查找。  
3、O (n \* log n )，这样的算法包括快速排序——一种速度较快的排序算法。  
4、O (n ² )，这样的算法包括选择排序——一种速度较慢的排序算法。  
5、O (n !)，这样的算法包括旅行商问题——一种非常慢的算法。

下面是分析算法时常见的函数分类列表。这些函数都处于n趋近于无穷大的情况下。按由快到慢的顺序排列。c是一个任意常数。

<table> 
 <tbody> 
 <tr> 
 <th>符号</th> 
 <th>名称 </th> 
 </tr> 
 <tr> 
 <td> <img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7b8d37856ce892bd7ee9a9f58ffea0febee5e9bc" alt="\mathrm {O} (1)\!"></td> 
 <td>常数（阶，下同） </td> 
 </tr> 
 <tr> 
 <td><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6c35c6c21c30a5643d3100b7993f907b58cf79cf" alt="\mathrm {O} (\log n)\!"></td> 
 <td>对数 </td> 
 </tr> 
 <tr> 
 <td><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1b59e14bd1ca3550ec4f649c41786884bbe368b5" alt="\mathrm {O} [(\log n)^{c}]\!"></td> 
 <td>多对数 </td> 
 </tr> 
 <tr> 
 <td><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8bc936ac28af050e96d7262b89eb11af36bcc958" alt="\mathrm {O} (n)\!"></td> 
 <td>线性，次线性 </td> 
 </tr> 
 <tr> 
 <td><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4d532063b672f55f3d9d24f9950d47278b837b22" alt="\mathrm {O} (n\log ^{*}n)\!"></td> 
 <td><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/566a9c5416bedcda38ab4993b73c3ea1b75c4ca9" alt="\log ^{*}n">为迭代对数 </td> 
 </tr> 
 <tr> 
 <td><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7ae44f69480d60cd1f7c67bcc189f608488a79dd" alt="\mathrm {O} (n\log n)\!"></td> 
 <td>线性对数，或对数线性、拟线性、超线性 </td> 
 </tr> 
 <tr> 
 <td><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b4a9cde84a808a1c8b6658032611f99e7fa0bb13" alt="\mathrm {O} (n^{2})\!"></td> 
 <td>平方 </td> 
 </tr> 
 <tr> 
 <td><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/086d08cc1d72e647e1810c0e2ac7e70d099fec37" alt="\mathrm {O} (n^{c}),\operatorname {Integer} (c>1)"></td> 
 <td>多项式，有时叫作“代数”（阶） </td> 
 </tr> 
 <tr> 
 <td><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a830bd28003689e75eb85a330c2017413dcceb98" alt="\mathrm {O} (c^{n})\!"></td> 
 <td>指数，有时叫作“几何”（阶） </td> 
 </tr> 
 <tr> 
 <td><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f5a7957bb5d704181437f3fcf22b257ecbe699a7" alt="\mathrm {O} (n!)\!"></td> 
 <td>阶乘，有时叫做“组合”（阶） </td> 
 </tr> 
 </tbody> 
</table>

**示例：**

# 下面3个变量的步数为O(1)*3=O(3)
    a=5							# O(1)
    b=6        					# O(1)
    c=10 						# O(1)
    
    # O(n)*(O(n)*(O(1)*3))=O(3n²)
    for i in range(n): 			# O(n)
       for j in range(n): 		# O(n)
          x = i * i 			# O(1)
          y = j * j 			# O(1)
          z = i * j  			# O(1)
    
    # O(n)*(O(1)*2)=O(2n)
    for k in range(n):			# O(n)
       w = a*k + 45 			# O(1)
       v = b*b 					# O(1)
    
    d = 33 						# O(1)

上述代码的总步数：O(3)+O(3n²)+O(2n)+O(1)=O(3n²+2n+4)，因当n很大时，其他均可忽略，  
所以上述代码的大O表示法为O(n²)。

**总结：**  
1、算法的速度指的并非是时间，而是操作数的增速。  
2、算法的运行时间用大O表示法表示。  
3、大O表示法表示对计算中的实际步数的近似。

**附：各种排序算法的时间、空间复杂度及稳定性**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4ODgyMzI3_size_16_color_FFFFFF_t_70_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4ODgyMzI3_size_16_color_FFFFFF_t_70_pic_center]: /images/20220220/62e2f643c8b342fab66d187e4b1887aa.png