資料結構初入門----演算法效率（時間復雜度、空間復雜度）

引言

首先大家肯定對資料結構是什么很好奇，下面就給大家來講一下什么是資料結構，

資料結構(data structure)是帶有結構特性的資料元素的集合，它研究的是資料的邏輯結構和資料的物理結構以及它們之間的相互關系，并對這種結構定義相適應的運算，設計出相應的演算法，并確保經過這些運算以后所得到的新結構仍保持原來的結構型別，
簡而言之，資料結構是相互之間存在一種或多種特定關系的資料元素的集合，即帶“結構”的資料元素的集合，“結構”就是指資料元素之間存在的關系，分為邏輯結構和存盤結構，

演算法效率

上述提到了演算法，那么什么是演算法？那么我們應該如何去衡量一個演算法的好壞呢？下面這篇文章就告訴大家：

演算法（Algorithm）是指解題方案的準確而完整的描述，是一系列解決問題的清晰指令，演算法代表著用系統的方法描述解決問題的策略機制，

演算法在撰寫成可執行程式后，運行時需要耗費時間資源和空間(記憶體)資源 ，因此衡量一個演算法的好壞，一般是從時間和空間兩個維度來衡量的，即時間復雜度和空間復雜度，
時間復雜度主要衡量一個演算法的運行快慢，而空間復雜度主要衡量一個演算法運行所需要的額外空間，

時間復雜度

時間復雜度的定義：在計算機科學中，演算法的時間復雜度是一個函式，它定量描述了該演算法的運行時間，一個演算法所花費的時間與其中陳述句的執行次數成正比例，演算法中的基本操作的執行次數，為演算法的時間復雜度，
即：找到某潭訓本陳述句與問題規模N之間的數學運算式，就是算出了該演算法的時間復雜度，

舉例說明：

// 請計算一下Func1中++count陳述句總共執行了多少次？
void Func1(int N)
{
	int count = 0;
	for (int i = 0; i < N ; ++ i)
	{
		for (int j = 0; j < N ; ++ j)
		{
			++count;
		}
	}
	for (int k = 0; k < 2 * N ; ++ k)
	{
		++count;
	}
	int M = 10;
	while (M--)
	{
		++count;
	}
	printf("%d\n", count);
}

按照上述的說法，我們可以算出上述函式執行的基本操作次數：
F(N) = N^2 + 2*N + 10
如若我們給N取以下值，可得：
N = 10 F(N) = 130
N = 100 F(N) = 10210
N = 1000 F(N) = 1002010
實際中我們計算時間復雜度時，我們其實并不一定要計算精確的執行次數，而只需要大概執行次數，那么這里我們使用大O的漸進表示法，

大O漸進表示法

大O符號（Big O notation）：是用于描述函式漸進行為的數學符號， 推導大O階方法：
1、用常數1取代運行時間中的所有加法常數，
2、在修改后的運行次數函式中，只保留最高階項，
3、如果最高階項存在且不是1，則去除與這個專案相乘的常數，得到的結果就是大O階，

當我們引入大O漸進表示法之后，上述函式的時間復雜度就可表示為：
O(N^2)
通過上面我們會發現大O的漸進表示法去掉了那些對結果影響不大的項，簡潔明了的表示出了執行次數，
另外有些演算法的時間復雜度存在最好、平均和最壞情況：
最壞情況：任意輸入規模的最大運行次數(上界)
平均情況：任意輸入規模的期望運行次數
最好情況：任意輸入規模的最小運行次數(下界)
例如：在一個長度為N陣列中搜索一個資料x
最好情況：1次找到
最壞情況：N次找到
平均情況：N/2次找到
在實際中一般情況關注的是演算法的最壞運行情況，所以陣列中搜索資料時間復雜度為O(N)

時間復雜度舉例

// 計算Func2的時間復雜度？
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);
}

基本操作執行了2N+10次，通過推導大O階方法知道，時間復雜度為 O(N)

// 計算Func3的時間復雜度？
void Func3(int N, int M)
{
	int count = 0;
	for (int k = 0; k < M; ++ k)
	{
		++count;
	}
	for (int k = 0; k < N ; ++ k)
	{
		++count;
	}
	printf("%d\n", count);
}

基本操作執行了M+N次，有兩個未知數M和N，時間復雜度為 O(N+M)

// 計算Func4的時間復雜度？
void Func4(int N)
{
	int count = 0;
	for (int k = 0; k < 100; ++ k)
	{
		++count;
	}
	printf("%d\n", count);
}

基本操作執行了10次，通過推導大O階方法，時間復雜度為 O(1)

// 計算strchr的時間復雜度？
const char * strchr ( const char * str, int character );

基本操作執行最好1次，最壞N次，時間復雜度一般看最壞，時間復雜度為 O(N)

// 計算BubbleSort的時間復雜度？
void BubbleSort(int* a, int n)
{
	assert(a);
	for (size_t end = n; end > 0; --end)
	{
		int exchange = 0;
		for (size_t i = 1; i < end; ++i)
		{
			if (a[i-1] > a[i])
			{
				Swap(&a[i-1], &a[i]);
				exchange = 1;
			}
		}
		if (exchange == 0)
		break;
	}
}

基本操作執行最好N次，最壞執行了(N*(N+1)/2次，通過推導大O階方法+時間復雜度一般看最壞，時間復雜度為 O(N^2)

// 計算BinarySearch的時間復雜度？
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;
}

基本操作執行最好1次，最壞O(logN)次，時間復雜度為 O(logN) ps：logN在演算法分析中表示是底數為2，對數為N，有些地方會寫成lgN，

// 計算階乘遞回Fac的時間復雜度？
long long Fac(size_t N)
{
	if(0 == N)
		return 1;
	return Fac(N-1)*N;
}

通過計算分析發現基本操作遞回了N次，時間復雜度為O(N)

// 計算斐波那契遞回Fib的時間復雜度？
long long Fib(size_t N)
{
	if(N < 3)
		return 1;
	return Fib(N-1) + Fib(N-2);
}

通過計算分析發現基本操作遞回了2^N次，時間復雜度為O(2 ^ N)

空間復雜度

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

空間復雜度舉例

// 計算BubbleSort的空間復雜度？
void BubbleSort(int* a, int n)
{
	assert(a);
	for (size_t end = n; end > 0; --end)
	{
		int exchange = 0;
		for (size_t i = 1; i < end; ++i)
		{
			if (a[i-1] > a[i])
			{
				Swap(&a[i-1], &a[i]);
				exchange = 1;
			}
		}
		if (exchange == 0)
			break;
	}
}

使用了常數個額外空間，所以空間復雜度為 O(1)

// 計算Fibonacci的空間復雜度？
// 回傳斐波那契數列的前n項
long long* Fibonacci(size_t n)
{
	if(n==0)
		return NULL;
	long long * fibArray = (long long *)malloc((n+1) * sizeof(long long));
	fibArray[0] = 0;
	fibArray[1] = 1;
	for (int i = 2; i <= n ; ++i)
	{
		fibArray[i] = fibArray[i - 1] + fibArray [i - 2];
	}
	return fibArray;
}

動態開辟了N個空間，空間復雜度為 O(N)

// 計算階乘遞回Fac的空間復雜度？
long long Fac(size_t N)
{
	if(N == 0)
		return 1;
	return Fac(N-1)*N;
}

遞回呼叫了N次，開辟了N個堆疊幀，每個堆疊幀使用了常數個空間，空間復雜度為O(N)，