算法的时间复杂度

深碍√TFBOYSˉ_ 2022-02-22 16:24 373阅读 0赞

### 文章目录 ###

*  1. 各典型时间复杂度关系
 *  2. 举例
 *   *  2.1 对数级复杂度：O( log ⁡ 2 n \\log\_2n log2n)
     *  2.2 线性复杂度：O(n)
     *  2.3 平方级复杂度：O( n 2 n^2 n2)
     *  2.4 立方级复杂度：O( n 3 n^3 n3)

**假设运行总次数为：3 n 2 n^2 n2 \+ 4n + 5**

<table> 
 <tbody> 
  <tr> 
   <th colspan="2">算法时间复杂度推算规则</th> 
  </tr> 
  <tr> 
   <th>步骤</th> 
   <th>举例</th> 
  </tr> 
  <tr> 
   <td>用常数 1 取代运行时间中的所有加法常数</td> 
   <td>3n^2 + 4n</td> 
  </tr> 
  <tr> 
   <td>在修改后的运行次数函数中，只保留最高阶项</td> 
   <td>3n^2</td> 
  </tr> 
  <tr> 
   <td>如果最高阶项存在且不是 1 ，则去除与这个项相乘的常数</td> 
   <td>n^2</td> 
  </tr> 
  <tr> 
   <th colspan="2">T（n） = O(n^2)</th> 
  </tr> 
 </tbody> 
</table>

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

# 1. 各典型时间复杂度关系 #

O(1) < O( log ⁡ 2 n \\log\_2n log2n) < O(n) < O(n  log ⁡ 2 n \\log\_2n log2n) < O( n 2 n^2 n2) < O( n 3 n^3 n3) < O( 2 n 2^n 2n)

# 2. 举例 #

## 2.1 对数级复杂度：O( log ⁡ 2 n \\log\_2n log2n) ##

int i = 0;
    while(i < n){
    	i *= 2;
    }

i 取值为：0，2，4，8，16，……  
第 k 次：i =  2 k 2^k 2k ；当 i =  2 k 2^k 2k >= n 的时候停止，k =  log ⁡ 2 n \\log\_2n log2n  
**T（n） = O( log ⁡ 2 n \\log\_2n log2n)**

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

## 2.2 线性复杂度：O(n) ##

for (int i = 0; i < n; i++)
    	printf("%d ", i);

程序一共执行 n 次，**T（n） = O(n)**

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

## 2.3 平方级复杂度：O( n 2 n^2 n2) ##

for (int i = 1; i <= n; i++)										//例2.3.1
    	for (int j = 1; j <= n; j++)
    		s++;
    
    for (int i = 1; i <= n; i++)									    //例2.3.2
    	for (int j = i; j <= n; j++)
    		s++;
    
    for (int i = 1; i <= n; i++)										//例2.3.3
    	for (int j = 1; j <= i; j++)
    		s++;

//例2.3.1

综上：一共是 n \* n 次，**T（n） = O( n 2 n^2 n2)**  
//例2.3.2

综上：一共是 1 + …… + (n - 1) + n = n(n + 1) / 2 次，**T（n） = O( n 2 n^2 n2)**  
//例2.3.3

综上：一共是 1 + 2 + …… + n = n(n + 1) / 2 次，**T（n） = O( n 2 n^2 n2)**

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

## 2.4 立方级复杂度：O( n 3 n^3 n3) ##

for (int i = 1; i <= n; i++)											
    	for (int j = 1; j <= i; j++)
    		for (int j = 1; k <= j; k++)
    			s++;

i = m时，内层共循环 1 + 2 + …… + m = m(m + 1) / 2 次

<table> 
 <thead> 
  <tr> 
   <th>i （取值）</th> 
   <th>k 层循环次数</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>1</td> 
   <td>1(1 + 1) / 2</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>2(2 + 1) / 2</td> 
  </tr> 
  <tr> 
   <td>3</td> 
   <td>3(3 + 1) / 2</td> 
  </tr> 
  <tr> 
   <td>……</td> 
   <td>……</td> 
  </tr> 
  <tr> 
   <td>n</td> 
   <td>n(n + 1) / 2</td> 
  </tr> 
 </tbody> 
</table>

将上表第二列n项相加：1/2（1 + …… + n +  1 2 1^2 12 \+ …… +  n 2 n^2 n2）= ……  
1²+2²+3²+……+n²=n(n+1)(2n+1)/6  
综上：**T（n） = O( n 3 n^3 n3)**