●🧑個人主頁:你帥你先說.
●📃歡迎點贊👍關注💡收藏💖
●📖既選擇了遠方，便只顧風雨兼程，
●🤟歡迎大家有問題隨時私信我！
●🧐著作權：本文由[你帥你先說.]原創，CSDN首發，侵權必究，

🍎1.演算法效率

🍖1.1如何衡量一個演算法的好壞

之前在C語言中我們學過求斐波那契數列，用了兩種方法，一種是遞回，一種是回圈，
對于遞回求斐波那契數列:

long long Fib(int N) 
{
 if(N < 3)
 return 1; 
 return Fib(N-1) + Fib(N-2);
}

我們知道，這個代碼寫起來比回圈要簡潔很多，但效率卻不高，因為遞回呼叫函式對記憶體的消耗非常大，
所以說簡潔的代碼不一定是好的，既簡潔又高效的代碼才是好的，

🍗1.2演算法的復雜度

演算法在撰寫成可執行程式后，運行時需要耗費時間資源和空間(記憶體)資源，因此衡量一個演算法的好壞，一般是從時間和空間兩個維度來衡量的，即時間復雜度和空間復雜度， 時間復雜度主要衡量一個演算法的運行快慢，而空間復雜度主要衡量一個演算法運行所需要的額外空間， 在計算機發展的早期，計算機的存盤容量很小，所以對空間復雜度很是在乎，但是經過計算機行業的迅速發展，計算機的存盤容量已經達到了很高的程度，所以我們如今已經不需要再特別關注一個演算法的空間復雜度，

🍊2.時間復雜度

🧇2.1時間復雜度的概念

時間復雜度的定義：在計算機科學中，演算法的時間復雜度是一個函式，它定量描述了該演算法的運行時間，一個演算法執行所耗費的時間，從理論上說，是不能算出來的，只有你把你的程式放在機器上跑起來，才能知道，但是我們需要每個演算法都上機測驗嗎？是可以都上機測驗，但是這很麻煩，所以才有了時間復雜度這個分析方式，一個演算法所花費的時間與其中陳述句的執行次數成正比例，演算法中的基本操作的執行次數，為演算法的時間復雜度，

// 請計算一下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);
}

Func1 執行的基本操作次數 ：
● N = 10 F(N) = 130
● N = 100 F(N) = 10210
● N = 1000 F(N) = 1002010
實際中我們計算時間復雜度時，我們其實并不一定要計算精確的執行次數，而只需要大概執行次數，那么這里我們使用大O的漸進表示法，

🍟2.2 大O的漸進表示法

大O符號（Big O notation）：是用于描述函式漸進行為的數學符號，
推導大O階方法：
1、用常數1取代運行時間中的所有加法常數，
2、在修改后的運行次數函式中，只保留最高階項，
3、如果最高階項存在且不是1，則去除與這個專案相乘的常數，得到的結果就是大O階，
使用大O的漸進表示法以后，Func1的時間復雜度為：
N = 10 F(N) = 100
N = 100 F(N) = 10000
N = 1000 F(N) = 1000000
通過上面我們會發現大O的漸進表示法去掉了那些對結果影響不大的項，簡潔明了的表示出了執行次數，
另外有些演算法的時間復雜度存在最好、平均和最壞情況：
最壞情況：任意輸入規模的最大運行次數(上界)
平均情況：任意輸入規模的期望運行次數
最好情況：任意輸入規模的最小運行次數(下界)
例如：在一個長度為N陣列中搜索一個資料x
最好情況：1次找到
最壞情況：N次找到
平均情況：N/2次找到
在實際中一般情況關注的是演算法的最壞運行情況，所以陣列中搜索資料時間復雜度為O(N)

🍔2.3常見時間復雜度計算舉例

// 計算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(N)，
這個時候你就會想：

別急，這才剛開始，

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);
}

相信大家的第一反應一定是O(M+N)，答案確實是這樣，
但我們這樣想的前提是什么？題目并沒有說M和N之間的大小關系，如果M的大小遠大于N，那么這題的答案就是O(N)，如果M和N相等或者是接近，可以寫成O(M)也可以寫成O(N)，因為題目沒有說明他們之間的大小，所以我們通常都寫成O(M+N)，

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

這道題是O(100)嗎?在這里要強調一下，這種常數次的時間復雜度我們一般用O(1)來表示，不是只執行了一次，是執行了常數次，

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

這個冒泡排序與上面的不同了，每一輪的次數都在變動，當i = 0時，執行了n-1次，當i = 1時，執行了n-2次，
n-1->n-2->n-3->…->2->1
這個式子用等引數列求和就能算出結果為 n ? ( n ? 1 ) 2 \frac{n*(n-1)}{2} 2n?(n?1)?
所以時間復雜度為O(n)，

// 計算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; 
}

這道題可能讓很多人懵了，時間復雜度怎么算？
我們先來分析一下二分查找的程序，二分查找每一次查找完都會邊界值相加然后除2，那么就相當于是n/2/2/2/2/2.....=1，那么n = 2*2*2*....2，假設有x個2，那就是n = 2 x 2^{x} 2x，兩邊同時取對數就是x = log ? 2 n \log_2n log2?n，
所以最終時間復雜度就是O( log ? 2 n \log_2n log2?n)，

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

這個執行的總次數我們容易計算出是N，
第一次呼叫Fac(N)
第二次呼叫Fac(N-1)
…
第N次呼叫Fac(1)
這里要說明一下遞回的總次數是遞回的次數*每次遞回中的操作次數，
什么意思呢？
如果這段代碼里再加一次執行10次的回圈，那總次數就是10*N，

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

這道題相對來說就比較復雜了，
2 0 2^{0} 20 Fib(N)
2 1 2^{1} 21 Fib(N-1) Fib(N-2)
2 2 2^{2} 22 Fib(N-2)Fib(N-3)Fib(N-3)Fib(N-4)
…
2 n ? 1 2^{n-1} 2n?1 Fib(1)Fib(0)
由等比數列的求和公式可求得次數為 2 n 2^{n} 2n-1-x，x是什么？因為靠后的列數在遞回時會比前面幾列的先遞回結束，所以要減去少算的那幾次，但對總次數沒有太大的影響，所以時間復雜度為O( 2 n 2^{n} 2n) ，

🍉3.空間復雜度

🌭3.1空間復雜度的概念

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

🌮3.2常見空間復雜度計算舉例

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

這個演算法的空間復雜度是O(1)，為什么呢？
空間復雜度算的是額外的空間的個數，*a和n是函式本身就具有的，額外的只有i、j、t，是常數個，所以空間復雜度為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+1個額外的空間，再看其它的臨時變數有i，所以是n+2個空間，所以空間復雜度是O(N)，

// 計算階乘遞回Fac的空間復雜度
long long Fac(size_t N) 
{
 	if(N == 1)
 	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);
}

很多人可能會這樣想，每次遞回一次都開辟一塊空間，所以和時間復雜度是一樣的，會認為是 O ( 2 N ) O(2^{N}) O(2N)，記住，空間是可以重復利用的，不累計，時間是一去不復返的，累計的，在遞回時，
2 0 2^{0} 20 Fib(N)
2 1 2^{1} 21 Fib(N-1) Fib(N-2)
2 2 2^{2} 22 Fib(N-2)Fib(N-3)Fib(N-3)Fib(N-4)
…
2 n ? 1 2^{n-1} 2n?1 Fib(1)Fib(0)
會先進行第一列的遞回，第一列遞回完第二列可以接著用第一列的空間，所以空間復雜度為O(N)，

講到這，資料結構的入門級內容就講完了，

🍉🍉🍉🍉🍉🍉🍉🍉🍉🍉🍉🍉🍉
這樣的文章你還不快點贊👍關注💡收藏💖
🥝🥝🥝🥝🥝🥝🥝🥝🥝🥝🥝🥝🥝