【零基礎學會資料結構】--時間復雜度與空間復雜度

什么是資料結構？

資料結構(Data structure)是計算機存盤，
組織資料的方式，指相互之間存在一種或多
種特定關系的資料元素的集合

什么是演算法？

演算法(Algorithm)：就是定義良好的計算程序
他取一個或一組的值為輸入，并產生一個或一
組的值作為輸出，簡單來說演算法就是一系列的
計算步驟，用來將輸入資料轉換成輸出的結果，

演算法效率

演算法在撰寫成可執行程式后，運行時需要耗費
時間資源和空間(記憶體)資源 ，因此衡量一個
演算法的好壞，一般是從時間和空間兩個維度來
衡量的，即時間復雜度和空間復雜度，但是因
為當今科技的發展，計算機的記憶體容量也在快
速發展，所以我們現在判斷一個演算法的好壞一
般是看其時間復雜度的大小

時間復雜度

時間復雜度的定義：在計算機科學中，演算法的
時間復雜度是一個函式，它定量描述了該演算法
的運行時間，但是因為外部因素如編譯機器的
不同，不同編譯機器下的編譯時間也存在差異
因此為了統一，我們不再計算一個演算法的運行
時間，而是計算一個演算法中基本陳述句的執行次
數，而一個演算法所花費的時間與其中陳述句的執
行次數成正比例，所以演算法中的基本操作的執
行次數，為演算法的時間復雜度，

如何計算一個演算法的執行時間

一個演算法的執行時間大致上等于其所有陳述句執
行時間的總和，而陳述句的執行時間則為該陳述句
重復執行的次數和執行一次所需的時間

舉例一

void Func1(int n){
for(i=1;i<=n;i++)    
 //頻度為n+1
    for(j=1;j<=n;j++){      
    //頻度為n*(n+1)
        c[i][j]=0;              
        //頻度為n^2
      for(k=1;k<=n;k++)          	
      //頻度為n^2*(n+1)
       c[i][j]=c[i][j]+a[i][k]*b[k][j] 
         //頻度為n^3
    }

}


該演算法中所有陳述句頻度之和，是矩陣階數n的函
數，用f(n)表示之，
    所以   f(n)=2n^3+3n^2+2n+1

對于舉例一這種比較簡單的演算法，可以直接計
算出演算法中所有陳述句的頻度，但是對于困難的
演算法則通常是比較困難的，實際我們在計算時
間復雜度的時候，可以只用演算法中的"**基本
陳述句**"的執行次數來計算演算法的作業量"**
基本陳述句**"指的是演算法中重復執行次數和算
法的執行時間成正比的陳述句(也稱為基本操作)
，如回圈陳述句.....同時我們也引進計算時間
復雜度的一個方法：大O漸進法，

大O漸近表示法

大O符號（Big O notation）：是用于描述
函式漸進行為的數學符號，

推導大O階法

1、用常數1取代運行時間中的所有加法常數， 
//如果一個演算法能計算出準確的一個次數，并
且這個數為常數，那么就用1代替,表示為
O(1)
2、在修改后的運行次數函式中，只保留最高
階項，
 //如n^2+n^3+3,只取最高階的，其他舍去，
 表示為O(n^2)
3、如果最高階項存在且不是1，則去除與這個
專案相乘的常數，得到的結果就是大
O階，
//如1/2*n,統一將系數變為1，表示為O(n)
使用大O的漸進表示法以后，Func1(舉例一)
的時間復雜度為：
    						O(n^3)
N = 10 F(N) = 1000
N = 100 F(N) = 1000000
N = 1000 F(N) = 1000000000
通過上面我們發現大O表示法去掉了那些對結
果影響不大的項，簡潔明了的表示了
執行次數
    
另外有些演算法的時間復雜度存在最好、平均和
最壞情況：
最壞情況：任意輸入規模的最大運行次數(上界)
平均情況：任意輸入規模的期望運行次數
最好情況：任意輸入規模的最小運行次數(下界)
例如：在一個長度為N陣列中搜索一個資料x
最好情況：1次找到
最壞情況：N次找到
平均情況：N/2次找到
在實際中一般情況關注的是演算法的最壞運行情
況，所以陣列中搜索資料時間復雜度為O(N)

舉例二(時間復雜度的計算)

void Func2(int N)
{
int count = 0;                          
for (int k = 0; k < 2 * N; ++k)
	{
		++count;
	}
	int M = 10;
	while (M--)
	{
		++count;
	}
	printf("%d\n", count);
}

Func2的基本操作次數為2n+10 ，根據大O漸
近法，這個演算法的時間復雜度為O(n).

舉例三(冒泡排序時間的時間復雜度)

void BubbleSort(int arr[], int len){
   int i, j, temp;
   for (j = 0; j < len - 1; j++){            
       for (i = 0; i < len - 1 - j; i++){    
          if(arr[i] > arr[i + 1]){            
             temp = arr[i];
             arr[i] = arr[i + 1];
             arr[i + 1] = temp;
             }
         }
     }
 }

冒泡排序的時間復雜度應該從思想上進行分析，
最好的情況下只排序一趟也就是n-1.最壞的情
況下整個陣列每個數都得進行排序，那么n個
數就得排序(n-1)+(n-2).....+1=n*(n+1)
/2次，時間復雜度就為O(n).

舉例四(二分查找演算法的時間復雜度)

int BinarySearch(int* a, int n, int x)
{
assert(a);
int begin = 0;
int end = n - 1;
while (begin < end)
{
int mid = begin + ((end - begin) >> 1);
if (a[mid] < x)
begin = mid + 1;
else if (a[mid] > x)
	end = mid;
else
	return mid;
	}
return -1;
}

二分查找演算法的時間復雜度也應從思想上進行
分析，假設要查找x次，最好的情況第一次就
找到，那么最壞情況就應該是最后一次找到
或者沒找到，根據二分演算法，每次的查找以
后都得折半，所以1*2*2*2....(x個2)=陣列
長度n，所以x就應該等于log2n

舉例五(遞回演算法的時間復雜度)

long long Fac(size_t N)
{
	if (0 == N)
		return 1;
	return Fac(N - 1) * N;
}


遞回演算法：遞回次數*遞回呼叫的次數
舉例五的基本操作執行了n次，所以時間復雜度
為O(n);

空間復雜度

空間復雜度也是一個數學運算式，是對一個算
法在運行程序中臨時占用存盤空間大小的量度 ，
空間復雜度不是程式占用了多少bytes的空間，
因為這個也沒太大意義，所以空間
復雜度算的是變數的個數，
空間復雜度計算規則基本跟實踐復雜度類似，
也使用大O漸進表示法，
注意：函式運行時所需要的堆疊空間(**存盤
引數,區域變數，一些暫存器資訊等**)
在編譯期間已經確定好了，此空間復雜度主
要通過**函式在運行**時候顯式申請的額外空
間**來確定，

舉例六(冒泡排序的空間復雜度)

void vBubbleSort(int arr[], int len){
  int i, j, temp;
    for (j = 0; j < len - 1; j++){            
       for (i = 0; i < len - 1 - j; i++){    
           if(arr[i] > arr[i + 1]){            
              temp = arr[i];
              arr[i] = arr[i + 1];
               arr[i + 1] = temp;
             }
         }
     }
 }


冒泡排序使用了常數個額外空間，所以空間復
雜度為1.

舉例八(遞回數列的空間復雜度）

long long Fac(size_t N)
{
	if (N == 0)
		return 1;
	return Fac(N - 1) * N;
}
Fac被呼叫了n次，創建了n個堆疊幀，每個堆疊幀
開辟了常數個空間，所以空間復雜度為O(n)

常見復雜度對比