目錄

一、什么是時間復雜度和空間復雜度？

1.演算法效率

2.時間復雜度的概念

3.空間復雜度的概念

4.復雜度計算在演算法的意義

二、如何計算常見演算法的時間復雜度？

推導大O階方法

復雜度對比

?

三、典型復雜度要求的演算法題練習

實體1

實體2

實體3

實體4

實體5：二分查找

實體6：單路遞回

實體7：多路遞回

結語

【前言】：前天有位鐵汁建議我更新資料結構這塊內容，原本我是打算放到兩個月之后的，不過呢那位老鐵是真的迫切，但是我精力有限，所以昨天晚上我認真想了一下，決定把零基礎搞定C語言系列壓縮一下，也就是說，C語言就不每個知識點都講一遍了，畢竟CSDN中有很多關于C語言優秀的文章，所以我直接把我認為重要的，以及一些易錯點寫出來，再夾帶著一些筆試題，這樣的話時間稍微充裕些，

【宣告】：資料結構已經拉開序幕咯，可能有點晚，但是筆者會盡量跟上的哦，鐵汁們上車了沒！？

嘿嘿，鐵汁們的要求我會盡量滿足的，不負代碼不負卿哦！

一、什么是時間復雜度和空間復雜度？

1.演算法效率

演算法效率分為兩種：第一種是時間效率，第二種是空間效率，時間效率被稱為時間復雜度， 而空間效率被稱作空間復雜度， 時間復雜度主要衡量的是一個演算法的運行速度，而空間復雜度主 要衡量一個演算法所需要的額外空間，在計算機發展的早期，計算機的存盤容量很小，所以對空間 復雜度很是在乎，但是經過計算機行業的迅速發展，計算機的存盤容量已經達到了很高的程度， 所以我們如今已經不需要再特別關注一個演算法的空間復雜度，

前面巴拉巴拉贅述了這么多，我們只需要知道，演算法效率分為兩種：一是時間效率，二是空間效率；時間效率被稱為時間復雜度， 而空間效率被稱作空間復雜度，

2.時間復雜度的概念

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

【敲黑板】：演算法中基本操作的執行次數，為演算法的時間復雜度，

3.空間復雜度的概念

空間復雜度是對一個演算法在運行程序中臨時占用存盤空間大小的量度 ，空間復雜度不是程式占用 了多少bytes的空間，因為這個也沒太大意義，所以空間復雜度算的是變數的個數

【敲黑板】：空間復雜度算的是變數的個數

注意注意，一定要注意：時間復雜度算的不是時間，算的是基本操作的執行次數；空間復雜度算的不是空間，算的是變數的個數，

4.復雜度計算在演算法的意義

其實很多公司在招聘的時候，資料結構和演算法這塊是考察的重點，在演算法筆試題里面幾乎都會考察應聘者對復雜度的計算和理解，所以，鐵汁們，這塊內容雖然不難，但卻是重點哦，不能掉以輕心！上面難理解或者是容易想錯的地方都已經明確標記出來咯，抓緊時間記住哈，加油加油！！

二、如何計算常見演算法的時間復雜度？

【敲黑板】：實際中我們計算時間復雜度時，我們其實并不一定要計算精確的執行次數，只需要大概執行次數，那么這里我們使用大O的漸進表示法，

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

推導大O階方法

1、用常數1取代運行時間中的所有常數，

2、在修改后的運行次數函式中，只保留最高階項，去除那些對結果影響不大的項

3、如果最高階項存在且不是1，則去除與這個專案相乘的常數，

得到的結果就是大O階，所以大O的漸進表示法只是一個估算，

可能你不是很理解上面推導大O階方法，沒關系，下面給出幾道例題，你很快就能理解啦！

//計算Func1基本操作執行了多少次
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++;
	}
}

Func1()基本操作的執行次數：

F(N) = N ^ 2 + 2 * N + 10 ;

隨著N的增大，N ^ 2對結果的影響是最大的

而時間復雜度只是一個估算，所以僅僅取決于運算式中對結果影響最大的那一項

所以，本題的時間復雜度為 O(N ^ 2)

另外有些演算法的時間復雜度存在最好、平均和最壞情況：

最壞情況：任意輸入規模的最大運行次數(上界)；

平均情況：任意輸入規模的期望運行次數；

最好情況：任意輸入規模的最小運行次數(下界)，

例如：在一個長度為N陣列中搜索一個資料x

最好情況：1次找到

最壞情況：N次找到

平均情況：N/2次找到

在實際中一般情況關注的是演算法的最壞運行情況，所以陣列中搜索資料時間復雜度為O(N）

復雜度對比

O(1)是最好的，其次是O(logN)...

常見的時間復雜度：

O(N) O(N ^ 2) O(log N) O(1)

而空間復雜度就不像時間復雜度這么復雜了，一般情況下空間復雜度都是O(1)，因為時間是累計的，而空間卻不是累計的，比如回圈走了n次，其實利用的是一個空間，因為變數往回走的時候，就會銷毀原先開辟的空間，現在暫時不理解也沒有關系，后面有大量的練習呢，

三、典型復雜度要求的演算法題練習

實體1

void Func2(int n)
{
	int count = 0;
	for (int k = 0; k < 2 * n; k++)
	{
		count++;
	}
	int m = 10;
	while (m--)
	{
		count++;
	}
}

Func2()基本操作的執行次數：

F(N) = 2 * N + 10

隨著N的增大，2 * N 對結果的影響是最大的，又因為其系數不是1，所以要去除與N相乘的常數2

所以，本題的時間復雜度為：O(N)

實體2

int Func(int n, int m)
{
	int count = 0;
	for (int k = 0; k < m; k++)
	{
		count++;
	}
	for (int i = 0; i < n; i++)
	{
		count++;
	}
}

Func3()基本操作的執行次數：

F(N) = m + n

如果說明m 遠大于 n, 則時間復雜度為O(M)；

如果說明m 約等于 n, 則時間復雜度為O(N)；

如果沒有說明，則時間復雜度為O(M + N)

實體3

void Func4(int n)
{
	int count = 0;
	for (int k = 0; k < 100; k++)
	{
		count++;
	}
}

可能你以為是O(100)，但是不是哦，是O(1)

實體4

const char* strchr(const char* str, char character)
{
	while (*str != '\0')
	{
		if (*str != character)
		{
			return str;
		}
		str++;
	}
	return NULL;
}

假設字串的長度為N，則本題時間復雜度為O(N)

實體5：二分查找

前提：陣列是有序的！！

int Binary_search(int* arr, int n, int k)
{
	int left = 0;
	int right = n - 1;
	int mid = 0;
	while (left <= right)
	{
		mid = (left + right) / 2;
		if (arr[mid] > k)
		{
			right = mid - 1;
		}
		else if (arr[mid] < k)
		{
			left = mid + 1;
		}
		else
		{
			return mid;
		}
	}
	return -1;
}

想象一張電費條：長度為n (n / 2^0)

第一次砍一半剩：n / 2 (n / 2^1)

第二次砍一半剩：n / 4 (n / 2^2)

第三次砍一半剩：n / 8 (n / 2^3)

...

假設砍了x次找到了：n / 2^x = 1

所以有，2^x = n ---> x = log n

所以二分查找的時間復雜度為：O(logN)

實體6：單路遞回

int func(int n)
{
	if (n == 1)
	{
		return 1;
	}
	return n + func(n - 1);
}

遞回呼叫了n次，每一次遞回運算的時間復雜度為O(1)，所以n次就是O(N)；

但是要注意的是，本題的空間復雜度不再是O(1)，

這里就需要補充一下遞回函式呼叫的知識點了，每次呼叫遞回函式都需要建立一個堆疊幀，而每個堆疊幀又都使用了常數個空間，遞回函式的空間復雜度取決于遞回呼叫堆疊的深度，所以很明顯，本題空間復雜度為O(N)

【敲黑板】：遞回函式呼叫時建立堆疊幀，回傳時銷毀，

實體7：多路遞回

斐波那契數列遞回：

題目描述：求斐波那契數列的第N項，1 1 2 3 5 8 13 21...

int fib(int n)
{
	if (n == 1 || n == 2)
	{
		return 1;
	}
	return fib(n - 1) + fib(n - 2);
}

本題非常典型，屬于多路遞回，可以將它畫成二叉樹的形式：

但是求時間復雜度的時候，我們要的是最壞的情況，所以假設成滿二叉樹，時間復雜度就是該二叉樹節點的個數，也就是O(2^N);

空間復雜度為這棵樹的高度，所以是O(N)

結語

資料結構第一章的內容到此結束咯，歡迎鐵汁們留言評論哈，你們的支持就是我最大的動力，當然啦，覺得有所識訓的鐵汁，麻煩動動小手，給俺個三聯吧，求求啦！