【数据结构与算法】三 █算法复杂度█ 一时间复杂度

小灰灰 2022-08-20 09:25 205阅读 0赞

# **【数据结构与算法】三 █算法复杂度█ 一 时间复杂度** #

上一篇文中提到反转 ,并通过一个小的算法实现了功能,当时的数组长度不到10,那么有几个不同的数组,我们怎么来判断算法在不同数组上所花费的时间与性能优越呢…  
**一个算法的评价主要从时间复杂度和空间复杂度来考虑。**

--------------------

# **时间复杂度 T(n)** #

n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。  
一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

我们以上篇中的算法为例进行说明

void reverse(T& array){
        int left = 0;
        int right = getArrayLen(array) - 1;
        int temp ;
        while(left < right){
            temp = array[left];
            array[left] = array[right];
            array[right] = temp;
            left ++;
            right --;
        }
    }

假设 方法体前3行语句 执行用时为2 ms .  
假设 n(array)的长度为10 (n=10) 那么while会执行5次, 所以循环次数为 n/2 .  
假设 while单次为10ms .  
所以 T(n) <= n/2 \* 10 + 2 ;  
在计算时间复杂度中,通常用 O(n) 表示 .

--------------------

# **大O符号 O(n)** #

在计算机科学中，它在分析算法复杂性的方面非常有用。

<table> 
 <thead> 
  <tr> 
   <th>符号</th> 
   <th align="center">名称</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>O(1)</td> 
   <td align="center">常数（阶，下同）</td> 
  </tr> 
  <tr> 
   <td>O(log*n)</td> 
   <td align="center">迭代对数</td> 
  </tr> 
  <tr> 
   <td>O(log n)</td> 
   <td align="center">对数</td> 
  </tr> 
  <tr> 
   <td>O[(log n)^c]</td> 
   <td align="center">多对数</td> 
  </tr> 
  <tr> 
   <td>O(n)</td> 
   <td align="center">线性，次线性</td> 
  </tr> 
  <tr> 
   <td>O(n log n)</td> 
   <td align="center">线性对数，或对数线性、拟线性、超线性</td> 
  </tr> 
  <tr> 
   <td>O(n^2)</td> 
   <td align="center">平方</td> 
  </tr> 
  <tr> 
   <td>O(n^c),Integer(c&gt;1)</td> 
   <td align="center">多项式，有时叫作“代数”（阶）</td> 
  </tr> 
  <tr> 
   <td>O(c^n)</td> 
   <td align="center">指数，有时叫作“几何”（阶）</td> 
  </tr> 
  <tr> 
   <td>O(n!)</td> 
   <td align="center">阶乘，有时叫做“组合”（阶）</td> 
  </tr> 
 </tbody> 
</table>

--------------------

# **最后** #

通过上面一些简单的讲解，  
相信朋友们已经知道其原理及特性了。  
本人能力有限,  
如发现错误或不合理欢迎指正…

--------------------