时间复杂度O(1) O(n) O(logn) O(nlogn)是什么意思？

￡神魔★判官ぃ 2023-10-07 16:19 13阅读 0赞

> 在你渐渐迷失在你的人生道路上的时候，千万不要因为走的太久，而忘记了我们为什么出发，做码农，也要清楚自己如何才能用有效的土地种植出 出色的产品，于是细节就需要把握一下。

如果你有兴趣可以关注一下公众号 biglead 我的大前端生涯，获取每日学习资料

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

在描述算法复杂度时，经常用到O(1), O(n), O(logn), O(nlogn)来表示对应复杂度程度，可以用于表示时间复杂度，也用于表示空间复杂度。

<table> 
 <thead> 
  <tr> 
   <th>类别</th> 
   <th>描述</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>O(1)</td> 
   <td>耗时与输入数据量大小无关</td> 
  </tr> 
  <tr> 
   <td>O(n)</td> 
   <td>数据量增大几倍，耗时也增大几位</td> 
  </tr> 
  <tr> 
   <td>O(n^2)</td> 
   <td>对 n 个数进行排序，需要扫描 n X n 次</td> 
  </tr> 
  <tr> 
   <td>O(logn)</td> 
   <td>当数据量增大 n 倍时 ，扫描次数增大 logn 次（以2为底数）</td> 
  </tr> 
  <tr> 
   <td>O(nlogn)</td> 
   <td></td> 
  </tr> 
 </tbody> 
</table>

时间复杂度的推导遵循3个原则：

*  如果运行时间跟n无关，是常数，则时间复杂度是O(1)；
 *  只保留时间函数中的最高阶项；
 *  去掉高阶项前面的系数；

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

##### 1 O(1) #####

若运行时间跟n的取值无关，即无论n取什么值，我的运行时间都不会变，则时间复杂度为O(1)，只要基本操作执行次数是个常量，时间复杂度都为O(1)。

##### 2 O(n)出现情况 #####

O(n)一般出现在只有一个循环的情况下，执行次数是线性的，如下：

public void test(int number) {
        
    	for(int i = 0 ; i < number ; i++) {
        
    		... 其他代码
    	}
    }

##### 3 O(n^2)出现情况 #####

O(n^2)一般出现在有嵌套循环的情况下

public void test(int n) {
        
        int a = 1;
        int b = 1;
    	for(int i = 0 ; i < n ; i++) {
        
    		for(int j = 0 ; j < n ; j++) {
        
    			a++;
    		}
    		b++;
    	}
    }

上术循环中执行次数是 n x n 次 ,时间复制度为O(n^2)