【数据结构-时间复杂度】

前言

���文主要介绍数据结构中时间复杂度的概念以及计算举例。

一、时间复杂度是什么？

算法效率是通过时间复杂度和空间复杂度来描述的。

时间复杂度：算法中所有语句被重复执行的次数，记为O(f(n))。

算法的时间复杂度不仅依赖于问题的规模n，也取决于待输入数据的性质（如输入数据元素的初始状态）。

//Q:如何理解”也取决于待输入数据的性质“
//A:下面的i--执行次数，就不仅取决于数组A的大小n,也取决于k的位置、是否有K(即输入数据元素的初始状态)
	i = n -1;
	while(i >= 0 && (A[i] != k))
		i--;
	return i;

二、举例计算时间复杂度

例1.

下面程序的时间复杂度是: O ( m ∗ n ) O(m*n) O(m∗n)

for(i = 0; i  
解析：
i = 1 内层 执行n次
i = 2 内层 执行n次
…
i = m 内层 执行n次
 
总计：
外层执行m次 ，内层执行m*n次，
共 
     
      
       
       
         O 
        
       
         ( 
        
       
         m 
        
       
         ∗ 
        
       
         n 
        
       
         ) 
        
       
         + 
        
       
         O 
        
       
         ( 
        
       
         m 
        
       
         ) 
        
       
         = 
        
       
         O 
        
       
         ( 
        
       
         m 
        
       
         ∗ 
        
       
         n 
        
       
         ) 
        
       
      
        O(m*n)+O(m) = O(m*n) 
       
      
    O(m∗n)+O(m)=O(m∗n)
 
例2.
 
下面程序的时间复杂度是： 
     
      
       
       
         O 
        
       
         ( 
        
        
        
          n 
         
        
          2 
         
        
       
         ) 
        
       
      
        O(n^2) 
       
      
    O(n2)
 
i = 0; s = 0;
while(++i 
	int p = 1;
	for(j=0; j