算法的时间复杂度表示法(大O表示法)

今天药忘吃喽~ 2022-11-21 01:06 215阅读 0赞

## 大 O 复杂度表示法 ##

算法的执行效率，粗略地讲，就是算法代码执行的时间。但是，如何在不运行代码的情况下，用“肉眼”得到一 段代码的执行时间呢？

for a in range(0, 1001):
     	for b in range(0, 1001): 
     		for c in range(0, 1001): 
    	 		if a**2 + b**2 == c**2 and a+b+c == 1000:
      				print("a, b, c: %d, %d, %d" % (a, b, c))

通过这段代码执行时间的推导过程，我们可以得到一个非常重要的规律，那就是，所有代码的执行时间 T(n) 与每 行代码的执行次数 n 成正比。  
![在这里插入图片描述][20201029101557894.png_pic_center]  
其中，T(n)表示代码执行的时间；n 表示数据规模的大小；f(n) 表示每行代码执行的次数总 和。因为这是一个公式，所以用 f(n) 来表示。公式中的 O，表示代码的执行时间 T(n) 与 f(n) 表达式成正比。  
`T(n) = O(n^3*2)` 这就是大 O 时间复杂度表示法,大 O 时间复杂度实际上并不具体表示代码真正的执行时 间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度。 当n很大时,你可以把它想象成 10000、100000。而公式中的低阶、常量、系数三部分并不左右增长趋势，所以 都可以忽略。我们只需要记录一个最大量级就可以了

#### 时间复杂度分析 ####

1.  只关注循环执行次数最多的一段代码

大 O 这种复杂度表示方法只是表示一种变化趋势。我们通常会忽略掉公式中的常量、低阶、系数，只需要记录一 个最大阶的量级就可以了。所以，我们在分析一个算法、一段代码的时间复杂度的时候，也只关注循环执行次数 最多的那一段代码就可以了。这段核心代码执行次数的 n 的量级，就是整段要分析代码的时间复杂度。

def cal(n): 
    	sum = 0 
    	i = 1
     	for i in rang(n+1): 
    		sum += i 
    		i+=1 
    	return sum

其中第 2、3 行代码都是常量级的执行时间，与 n 的大小无关，所以对于复杂度并没有影响。循环执行次数最多 的是第 4、5 行代码，所以这块代码要重点分析。前面我们也讲过，这两行代码被执行了 n 次，所以总的时间复 杂度就是 O(n)。

1.  加法法则：总复杂度等于量级最大的那段代码的复杂度

def cal(n): 
    	 sum = 0
    	 i = 1 
    
    	for in range(100): 
    		sum += i 
    
    	for i in rang(n+1): 
    		sum += i 
    		i+=1 
    
    	for i in range(n+1): 
    		for j in range(n+1): 
    			pass

综合这三段代码的时间复杂度，我们取其中最大的量级。所以，整段代码的时间复杂度就为 O(n2)。也就是说： 总的时间复杂度就等于量级最大的那段代码的时间复杂度

##### 最坏时间复杂度 #####

分析算法时，存在几种可能的考虑：

*  算法完成工作最少需要多少基本操作，即最优时间复杂度
 *  算法完成工作最多需要多少基本操作，即最坏时间复杂度
 *  算法完成工作平均需要多少基本操作，即平均时间复杂度

对于最优时间复杂度，其价值不大，因为它没有提供什么有用信息，其反映的只是最乐观最理想的情况，没有参考价值。  
对于最坏时间复杂度，提供了一种保证，表明算法在此种程度的基本操作中一定能完成工作。  
对于平均时间复杂度，是对算法的一个全面评价，因此它完整全面的反映了这个算法的性质。但另一方面，这种衡量并没有保证，不是每个计算都能在这个基本操作内完成。而且，对于平均情况的计算，也会因为应用算法的 实例分布可能并不均匀而难以计算。 因此，我们主要关注算法的最坏情况，亦即最坏时间复杂度。

#### 常见时间复杂度 ####

常见的复杂度并不多，从低阶到高阶有：O(1)、O(logn)、O(n)、O(nlogn)、O(n2)。

<table> 
 <thead> 
  <tr> 
   <th>执行次数函数举例</th> 
   <th>阶</th> 
   <th>非正式术语</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>12</td> 
   <td>O(1)</td> 
   <td>常数阶</td> 
  </tr> 
  <tr> 
   <td>2n + 3</td> 
   <td>O(n)</td> 
   <td>线性阶</td> 
  </tr> 
  <tr> 
   <td>3n^2 + 3n + 1</td> 
   <td>O(n^2)</td> 
   <td>平方阶</td> 
  </tr> 
  <tr> 
   <td>log2n + 20</td> 
   <td>O(logn)</td> 
   <td>对数阶</td> 
  </tr> 
  <tr> 
   <td>2n+3nlog2n+19</td> 
   <td>O(nlogn)</td> 
   <td>nlogn阶</td> 
  </tr> 
  <tr> 
   <td>2^n</td> 
   <td>O(2^n)</td> 
   <td>指数阶</td> 
  </tr> 
 </tbody> 
</table>

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDE5MTQz_size_16_color_FFFFFF_t_70_pic_center]

[20201029101557894.png_pic_center]: /images/20221120/0d84ce977a484cde9fcd710fb782840d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDE5MTQz_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20201029104041860.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDE5MTQz,size_16,color_FFFFFF,t_70#pic_center