C++ 超詳細分析資料結構中的時間複雜度

別彆著急划走哈，如果你跟我一樣是大學生，那麼你發現了一個寶藏！我們往後看-->

什麼是時間複雜度和空間複雜度

要想了解時間複雜度和空間複雜度，我們得知道什麼是時間複雜度和空間複雜度！

有的人看到這就明白了，而有的人卻去追求它的內涵：

見名知意嘛，時間複雜度不就是表示一個演演算法執行完所需要的時間？這還用問？錯錯錯！

        我來舉一個很簡單的例子：你家隔壁老王買了一臺 i9 12900k 和 RTX3080Ti 整個64GB的記憶體，你眼瞅著你 4G的記憶體，洋垃圾的處理器，開啟個PS都要冒煙的那種，來來來，你跟我說說能比嗎？

        所以簡單來說，時間複雜度主要衡量的是一個演演算法的執行速度，在電腦科學中，演演算法的時間複雜度其實是一個函數，他定量描述了該演演算法的執行時間。一個演演算法執行所耗費的時間。從理論上來說，是不能被算出來的，只有你把你的程式放在機器上跑起來才能知道，但是我們不需要每個演演算法都上機測試，所以才有了時間複雜度這個分析方式。一個演演算法所花費的時間與其中語句的執行次數成正比例，演演算法中的基本操作的執行次數，為演演算法的時間複雜度。

我們再來看空間複雜度-->

有了上面的案例，我們要做一個有內涵的程式猿，空間複雜度絕不是一個程式佔用了多少bytes的空間！

空間複雜度是用來衡量一個演演算法所需的額外空間！我們早期的計算機容量很小，在那個時候對空間複雜可謂是很在乎，但是現在隨著計算機的發展，現在我們都是在用空間換時間，所以我們如今已經不需要再特別關注一個演演算法的空間複雜度！

簡單做個總結:時間複雜度算的是基本操作的執行次數，空間複雜度算的是變數的個數！

有的小夥伴看到這蠻開心，懂了。 但是不著急，我們下面來看如何計算常見的空間複雜度和時間複雜度！

如何計算時間複雜度和空間複雜度

我們直接上程式碼！

// 請計算一下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;
	}
	printf("%dn", count);
}

算Func1執行了多少次？由上面講的可知，要我們算的就是時間複雜度！

 我們可以看到第一個大for迴圈執行次數是N²次，第二個for迴圈執行次數是2*N次，下面while 迴圈M是等於10的，所以會執行10次，由此可見 F(N) = N² + 2 * N + 10

        但是實際中我們計算時間複雜度時，我們並不需要計算準確的執行次數，只需要大概執行次數，這裡我們用大O的漸進表示法。

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

推導大O階的方法：

1、用常數1取代執行時間中的所有加法常數。

2、在修改後的執行次數函數中，只保留最高階項。

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

通過上面我們會發現大O的漸進表示法去掉了那些對結果影響不大的項，簡潔明瞭的表示出了執行次數。

使用大O的漸進表示法以後，Func1的時間複雜度為：O(N²)

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

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

最好情況：一次找到                   

最壞情況：N次找到                   

平均情況：N/2次找到

我們在實際中一般情況關注的是演演算法的最壞執行情況！，所以陣列中搜尋資料時間複雜度為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;
	}
}

由上邊可知，空間複雜度算的是變數的個數。空間複雜度計算規則基本跟時間複雜度類似，也使用大O漸進表示法。

據題意我們可知，形參*a， n 函數內部建立了變數 end， i， exchange使用了5個額外空間，所以根據推導大O階的方法可知空間複雜度為O(1)。

下面給大家總結下複雜度對比的圖：

如何計算時間複雜度和空間複雜度

        相信看完上邊的小夥伴們已經按耐不住想要寫程式碼了，接下來我們來看兩道有複雜度要求的演演算法題練習題，相信你聽我分析完會豎起大拇指說：妙啊！

話不多說直接上題目！！！

題目1：陣列nums包含從0到n的所有整數，但其中缺了一個。請編寫程式碼找出那個缺失的整數。你有辦法在O(n)時間內完成嗎？

題目來源:面試題 17.04. 消失的數位 - 力扣（LeetCode） (leetcode-cn.com)

輸入：[9,6,4,2,3,5,7,0,1]
輸出：8

思路1：先排序 -> 0 1 2 3 4 5 6  8 9   然後直接遍歷，判斷後一個數是不是比前一個數大1，就直    接找到了！但是！時間複雜度不符合題目要求，最快的排序 O(N*logN)

思路2：把0~N的數加起來結果是ret1,再把陣列中的數加起來是ret2，ret1-ret2就是我們要找的數!

思路3：互斥或 - 陣列中的數依次跟0~N的有所數互斥或，最後剩下的資料就是缺的那個數位！

最後我們來實現這道題的程式碼：

int missingNumber(int* nums, int numsSize)
{
	int x = 0;
	//先跟陣列中的值互斥或
	for (int i = 0; i < numsSize; ++i)
	{
		x ^= nums[i];
	}
	//再跟[0, N]之間的數互斥或
	for (int j = 0; j < numsSize + 1; ++j)
	{
		x ^= j;
	}
	return x;
}

看到這先別說妙，我們接著看下一道題！ 

題目2：給你一個陣列，將陣列中的元素向右輪轉 k 個位置，其中 k 是非負數。

你可以使用空間複雜度為 O(1) 的 原地 演演算法解決這個問題嗎？

輸入: nums = [1,2,3,4,5,6,7], k = 3

輸出: [5,6,7,1,2,3,4]

解釋:

向右輪轉 1 步: [7,1,2,3,4,5,6]

向右輪轉 2 步: [6,7,1,2,3,4,5]

向右輪轉 3 步: [5,6,7,1,2,3,4]

 題目來源:189. 輪轉陣列 - 力扣（LeetCode） (leetcode-cn.com)

思路1： 旋轉k次，先把陣列nums最後一個元素放到一個臨時變數tmp，然後從倒數第二個元素往後移動，再把 tmp 存的最後一個元素的值賦給陣列nums[0]。缺陷：效率低，時間複雜度為O(N*K)

思路2：用空間換時間，開闢一個跟nums一樣大的陣列出來，先把後k個放到新陣列，再把前k個接著放入新陣列，時間複雜度為O(N)，但是空間複雜度為O(N)，不符合題意！

思路3：後k個逆置，前n-k個逆置，再整體逆置！

最後我們來實現這道題的程式碼：

void Revers(int* nums, int left, int right)
{
	while (left < right)
	{
		int tmp = nums[left];
		nums[left] = nums[right];
		nums[right] = tmp;
		++left;
		--right;
	}
}
 
void rotat(int* nums, int numsSize, int k)
{
	if (k >= numsSize)
	{
		k %= numsSize;
	}
	Revers(nums, numsSize - k, numsSize - 1);
	Revers(nums, 0, numsSize - k - 1);
	Revers(nums, 0, numsSize- 1);
}

完結撒花！！！！

動動發財的小手，留個關注留個贊，我們快樂程式設計不頭禿。

gitee(碼雲)：Mercury. (zzwlwp) - Gitee.com

到此這篇關於C++ 超詳細分析資料結構中的時間複雜度的文章就介紹到這了,更多相關C++ 時間複雜度內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！