最通俗易懂的------------时间复杂度

港控/mmm° 2022-04-18 03:20 193阅读 0赞

# 一、时间复杂度 #

1.  **是什么**？  
    是表示执行某个算法所需要的计算工作量
2.  **用什么表示与官方定义**？  
    渐进时间复杂度（大O表示法）：若存在函数 f（n），使得当n趋近于 无穷大时，T（n）/ f（n）的极限值为不等于零的常数，则称 f（n）是T（n）的同数量级函数。记作 T（n）= O（f（n）），称O（f（n）） 为算法的渐进时间复杂度，简称时间复杂度。  
    PS:看的头疼代表你还是个正常人，记住红色字体内容，然后跟着下面例子走就行了。
3.  **四个通俗易懂的例子**

<table style="width:426.1pt;"> 
 <tbody> 
 <tr> 
 <td style="vertical-align:top;width:426.1pt;"> 
 <ol> 
 <li>吃的例子：N个香蕉2天吃一个，吃完需要几天？ void eat1(int n){ &nbsp;&nbsp;for(int i=0; i&lt;n; i++){; &nbsp;&nbsp;&nbsp;&nbsp;System.out.println("等待一天");&nbsp;&nbsp;&nbsp;&nbsp;//n次 &nbsp;&nbsp;&nbsp;&nbsp;System.out.println("吃一个香蕉");&nbsp;&nbsp;//n次 &nbsp;&nbsp;} }</li> 
 </ol>执行次数：T(n)=2n </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:426.1pt;"> &nbsp; void eat2(int n){ &nbsp;for(int i=1; i&lt;n; i*=2){ &nbsp;&nbsp;&nbsp;&nbsp;System.out.println("等待一天");&nbsp;&nbsp;&nbsp;&nbsp;//2^x≈n &nbsp;--&gt;x≈log2^n &nbsp;&nbsp;&nbsp;&nbsp;System.out.println("等待一天");&nbsp;&nbsp;&nbsp;&nbsp;//x≈log2^n &nbsp;&nbsp;&nbsp;&nbsp;System.out.println("等待一天");&nbsp;&nbsp;&nbsp;&nbsp;//x≈log2^n &nbsp;&nbsp;&nbsp;&nbsp;System.out.println("吃一半香蕉");&nbsp;&nbsp;//x≈log2^n &nbsp;&nbsp;} } 执行次数：T(n)=4*log2^n </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:426.1pt;"> 
 <ol> 
 <li>吃的例子：N个香蕉，1个柚子，两天吃掉一个柚子，吃完柚子需要几天？ void eat3(int n){ &nbsp;&nbsp;System.out.println("等待一天");&nbsp;&nbsp;&nbsp;&nbsp;//1 &nbsp;&nbsp;System.out.println("吃一个柚子");&nbsp;&nbsp;//1 }</li> 
 </ol>执行次数：T(n)=2 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:426.1pt;"> 
 <ol> 
 <li>吃的例子：N个柚子，吃掉第一个柚子需要1天，第二个需要2天，一次类推，吃完需要几天？ void eat4(int n){ &nbsp;&nbsp;for(int i=0; i&lt;n; i++){ &nbsp;&nbsp;&nbsp;&nbsp;for(int j=0; j&lt;i; j++){ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;System.out.println("等待一天");&nbsp;//1+2+3+4+...+n-1 &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;System.out.println("吃一个柚子");&nbsp;//n &nbsp;&nbsp;} }</li> 
 </ol>执行次数：T(n)=&nbsp;1+2+3+......+ n-1 + n = (1+n)*n/2 = 0.5n^2 + 0.5n </td> 
 </tr> 
 </tbody> 
</table>

4.**如何推导出时间复杂度**？

①.如果运行时间实常数级，用常数1表示

②.只保留时间函数中的最高阶项

③.如果最高阶项存在，则省去最高阶项前面的系数

5.**上四个例子的时间复杂度为**：

①T(n)=2n  最高阶项为2n，省去系数2，转化的时间复杂度为：**T(n) = O(n)  
                 图解：**  
               ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NjU3OTA5_size_16_color_FFFFFF_t_70][]

②T(n)=4\*log2^n   最高阶项为4\*log2^n，省去系数4，转化的时间复杂度为：**T(n) = O(log2^n)  
                 图解：  
                **![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NjU3OTA5_size_16_color_FFFFFF_t_70 1][]

③T(n)=2    只有常数量级，转化的时间复杂度为:**T(n) = O(1)**

**                 图解：**

**                **![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NjU3OTA5_size_16_color_FFFFFF_t_70 2][]

④T（n） = 0.5n^2 + 0.5n      最高阶项为0.5n^2，省去系数0.5，转化的时间复杂度为：**T（n） = O（n^2）**

**                 图解：**

**                **![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NjU3OTA5_size_16_color_FFFFFF_t_70 3][]

总：由上可以得出根据N值的不同，算法的时间复杂度在不同的N值区间内会有区别，所以根据不同的情况设计不同的算法是非常必要的。

[https://me.csdn.net/qq\_39657909][https_me.csdn.net_qq_39657909]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NjU3OTA5_size_16_color_FFFFFF_t_70]: /images/20220418/fa5c87d7f8184f0e9edfffabba99592a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NjU3OTA5_size_16_color_FFFFFF_t_70 1]: /images/20220418/efcbd0d806724bbea33bf73f13ff75d0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NjU3OTA5_size_16_color_FFFFFF_t_70 2]: /images/20220418/ba5fcb37e2934f72b44d624ddf7698f1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NjU3OTA5_size_16_color_FFFFFF_t_70 3]: /images/20220418/62d2e1b721c54737aef1d59ad11a7125.png
[https_me.csdn.net_qq_39657909]: https://me.csdn.net/qq_39657909