快捷導(dǎo)航

C++?超詳細(xì)分析數(shù)據(jù)結(jié)構(gòu)中的時(shí)間復(fù)雜度

更新時(shí)間：2022年03月24日 11:30:29 作者：程序猿教你打籃球

時(shí)間復(fù)雜度一般指時(shí)間復(fù)雜性。?在計(jì)算機(jī)科學(xué)中，時(shí)間復(fù)雜性，又稱時(shí)間復(fù)雜度，算法的時(shí)間復(fù)雜度是一個(gè)函數(shù)，它定性描述該算法的運(yùn)行時(shí)間

什么是時(shí)間復(fù)雜度和空間復(fù)雜度

要想了解時(shí)間復(fù)雜度和空間復(fù)雜度，我們得知道什么是時(shí)間復(fù)雜度和空間復(fù)雜度！

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

見(jiàn)名知意嘛，時(shí)間復(fù)雜度不就是表示一個(gè)算法運(yùn)行完所需要的時(shí)間？這還用問(wèn)？錯(cuò)錯(cuò)錯(cuò)！

我來(lái)舉一個(gè)很簡(jiǎn)單的例子：你家隔壁老王買了一臺(tái) i9 12900k 和 RTX3080Ti 整個(gè)64GB的內(nèi)存，你眼瞅著你 4G的內(nèi)存，洋垃圾的處理器，打開(kāi)個(gè)PS都要冒煙的那種，來(lái)來(lái)來(lái)，你跟我說(shuō)說(shuō)能比嗎？

所以簡(jiǎn)單來(lái)說(shuō)，時(shí)間復(fù)雜度主要衡量的是一個(gè)算法的運(yùn)行速度，在計(jì)算機(jī)科學(xué)中，算法的時(shí)間復(fù)雜度其實(shí)是一個(gè)函數(shù)，他定量描述了該算法的運(yùn)行時(shí)間。一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間。從理論上來(lái)說(shuō)，是不能被算出來(lái)的，只有你把你的程序放在機(jī)器上跑起來(lái)才能知道，但是我們不需要每個(gè)算法都上機(jī)測(cè)試，所以才有了時(shí)間復(fù)雜度這個(gè)分析方式。一個(gè)算法所花費(fèi)的時(shí)間與其中語(yǔ)句的執(zhí)行次數(shù)成正比例，算法中的基本操作的執(zhí)行次數(shù)，為算法的時(shí)間復(fù)雜度。

我們?cè)賮?lái)看空間復(fù)雜度-->

有了上面的案例，我們要做一個(gè)有內(nèi)涵的程序猿，空間復(fù)雜度絕不是一個(gè)程序占用了多少bytes的空間！

空間復(fù)雜度是用來(lái)衡量一個(gè)算法所需的額外空間！我們?cè)缙诘挠?jì)算機(jī)容量很小，在那個(gè)時(shí)候?qū)臻g復(fù)雜可謂是很在乎，但是現(xiàn)在隨著計(jì)算機(jī)的發(fā)展，現(xiàn)在我們都是在用空間換時(shí)間，所以我們?nèi)缃褚呀?jīng)不需要再特別關(guān)注一個(gè)算法的空間復(fù)雜度！

簡(jiǎn)單做個(gè)總結(jié):時(shí)間復(fù)雜度算的是基本操作的執(zhí)行次數(shù)，空間復(fù)雜度算的是變量的個(gè)數(shù)！

有的小伙伴看到這蠻開(kāi)心，懂了。但是不著急，我們下面來(lái)看如何計(jì)算常見(jiàn)的空間復(fù)雜度和時(shí)間復(fù)雜度！

如何計(jì)算時(shí)間復(fù)雜度和空間復(fù)雜度

我們直接上代碼！

// 請(qǐng)計(jì)算一下Func1基本操作執(zhí)行了多少次？
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執(zhí)行了多少次？由上面講的可知，要我們算的就是時(shí)間復(fù)雜度！

我們可以看到第一個(gè)大for循環(huán)執(zhí)行次數(shù)是N²次，第二個(gè)for循環(huán)執(zhí)行次數(shù)是2*N次，下面while 循環(huán)M是等于10的，所以會(huì)執(zhí)行10次，由此可見(jiàn) F(N) = N² + 2 * N + 10

但是實(shí)際中我們計(jì)算時(shí)間復(fù)雜度時(shí)，我們并不需要計(jì)算準(zhǔn)確的執(zhí)行次數(shù)，只需要大概執(zhí)行次數(shù)，這里我們用大O的漸進(jìn)表示法。

大O符號(hào)（Big O notation）：是用于描述函數(shù)漸進(jìn)行為的數(shù)學(xué)符號(hào)。

推導(dǎo)大O階的方法：

1、用常數(shù)1取代運(yùn)行時(shí)間中的所有加法常數(shù)。

2、在修改后的運(yùn)行次數(shù)函數(shù)中，只保留最高階項(xiàng)。

3、如果最高階項(xiàng)存在且不是1，則去除與這個(gè)項(xiàng)目相乘的常數(shù)。得到的結(jié)果就是大O階。

通過(guò)上面我們會(huì)發(fā)現(xiàn)大O的漸進(jìn)表示法去掉了那些對(duì)結(jié)果影響不大的項(xiàng)，簡(jiǎn)潔明了的表示出了執(zhí)行次數(shù)。

使用大O的漸進(jìn)表示法以后，F(xiàn)unc1的時(shí)間復(fù)雜度為：O(N²)

另外有些算法的時(shí)間復(fù)雜度存在最好、平均和最壞情況：

比如：在一個(gè)長(zhǎng)度為N數(shù)組中搜索一個(gè)數(shù)據(jù) x

最好情況：一次找到

最壞情況：N次找到

平均情況：N/2次找到

我們?cè)趯?shí)際中一般情況關(guān)注的是算法的最壞運(yùn)行情況！，所以數(shù)組中搜索數(shù)據(jù)時(shí)間復(fù)雜度為O(N)

我們接著上代碼！

// 計(jì)算BubbleSort的空間復(fù)雜度？
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;
	}
}

由上邊可知，空間復(fù)雜度算的是變量的個(gè)數(shù)?？臻g復(fù)雜度計(jì)算規(guī)則基本跟時(shí)間復(fù)雜度類似，也使用大O漸進(jìn)表示法。

據(jù)題意我們可知，形參*a， n 函數(shù)內(nèi)部創(chuàng)建了變量 end， i， exchange使用了5個(gè)額外空間，所以根據(jù)推導(dǎo)大O階的方法可知空間復(fù)雜度為O(1)。

下面給大家總結(jié)下復(fù)雜度對(duì)比的圖：

如何計(jì)算時(shí)間復(fù)雜度和空間復(fù)雜度

相信看完上邊的小伙伴們已經(jīng)按耐不住想要寫(xiě)代碼了，接下來(lái)我們來(lái)看兩道有復(fù)雜度要求的算法題練習(xí)題，相信你聽(tīng)我分析完會(huì)豎起大拇指說(shuō)：妙啊！

話不多說(shuō)直接上題目?。。?/p>

題目1：數(shù)組nums包含從0到n的所有整數(shù)，但其中缺了一個(gè)。請(qǐng)編寫(xiě)代碼找出那個(gè)缺失的整數(shù)。你有辦法在O(n)時(shí)間內(nèi)完成嗎？

題目來(lái)源:面試題 17.04. 消失的數(shù)字 - 力扣（LeetCode） (leetcode-cn.com)

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

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

思路2：把0~N的數(shù)加起來(lái)結(jié)果是ret1,再把數(shù)組中的數(shù)加起來(lái)是ret2，ret1-ret2就是我們要找的數(shù)!

思路3：異或 - 數(shù)組中的數(shù)依次跟0~N的有所數(shù)異或，最后剩下的數(shù)據(jù)就是缺的那個(gè)數(shù)字！

最后我們來(lái)實(shí)現(xiàn)這道題的代碼：

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

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

題目2：給你一個(gè)數(shù)組，將數(shù)組中的元素向右輪轉(zhuǎn) k 個(gè)位置，其中 k 是非負(fù)數(shù)。

你可以使用空間復(fù)雜度為 O(1) 的原地算法解決這個(gè)問(wèn)題嗎？

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

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

解釋:

向右輪轉(zhuǎn) 1 步: [7,1,2,3,4,5,6]

向右輪轉(zhuǎn) 2 步: [6,7,1,2,3,4,5]

向右輪轉(zhuǎn) 3 步: [5,6,7,1,2,3,4]

題目來(lái)源:189. 輪轉(zhuǎn)數(shù)組 - 力扣（LeetCode） (leetcode-cn.com)

思路1：旋轉(zhuǎn)k次，先把數(shù)組nums最后一個(gè)元素放到一個(gè)臨時(shí)變量tmp，然后從倒數(shù)第二個(gè)元素往后移動(dòng)，再把 tmp 存的最后一個(gè)元素的值賦給數(shù)組nums[0]。缺陷：效率低，時(shí)間復(fù)雜度為O(N*K)

思路2：用空間換時(shí)間，開(kāi)辟一個(gè)跟nums一樣大的數(shù)組出來(lái)，先把后k個(gè)放到新數(shù)組，再把前k個(gè)接著放入新數(shù)組，時(shí)間復(fù)雜度為O(N)，但是空間復(fù)雜度為O(N)，不符合題意！

思路3：后k個(gè)逆置，前n-k個(gè)逆置，再整體逆置！

最后我們來(lái)實(shí)現(xiàn)這道題的代碼：

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

完結(jié)撒花?。。?！

動(dòng)動(dòng)發(fā)財(cái)?shù)男∈?，留個(gè)關(guān)注留個(gè)贊，我們快樂(lè)編程不頭禿。

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

到此這篇關(guān)于C++ 超詳細(xì)分析數(shù)據(jù)結(jié)構(gòu)中的時(shí)間復(fù)雜度的文章就介紹到這了,更多相關(guān)C++ 時(shí)間復(fù)雜度內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: