C++?超詳細(xì)分析數(shù)據(jù)結(jié)構(gòu)中的時(shí)間復(fù)雜度
別別著急劃走哈,如果你跟我一樣是大學(xué)生,那么你發(fā)現(xiàn)了一個(gè)寶藏!我們往后看-->
什么是時(shí)間復(fù)雜度和空間復(fù)雜度
要想了解時(shí)間復(fù)雜度和空間復(fù)雜度,我們得知道什么是時(shí)間復(fù)雜度和空間復(fù)雜度!
有的人看到這就明白了,而有的人卻去追求它的內(nèi)涵:
見名知意嘛,時(shí)間復(fù)雜度不就是表示一個(gè)算法運(yùn)行完所需要的時(shí)間?這還用問?錯(cuò)錯(cuò)錯(cuò)!
我來舉一個(gè)很簡單的例子:你家隔壁老王買了一臺 i9 12900k 和 RTX3080Ti 整個(gè)64GB的內(nèi)存,你眼瞅著你 4G的內(nèi)存,洋垃圾的處理器,打開個(gè)PS都要冒煙的那種,來來來,你跟我說說能比嗎?
所以簡單來說,時(shí)間復(fù)雜度主要衡量的是一個(gè)算法的運(yùn)行速度,在計(jì)算機(jī)科學(xué)中,算法的時(shí)間復(fù)雜度其實(shí)是一個(gè)函數(shù),他定量描述了該算法的運(yùn)行時(shí)間。一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間。從理論上來說,是不能被算出來的,只有你把你的程序放在機(jī)器上跑起來才能知道,但是我們不需要每個(gè)算法都上機(jī)測試,所以才有了時(shí)間復(fù)雜度這個(gè)分析方式。一個(gè)算法所花費(fèi)的時(shí)間與其中語句的執(zhí)行次數(shù)成正比例,算法中的基本操作的執(zhí)行次數(shù),為算法的時(shí)間復(fù)雜度。
我們再來看空間復(fù)雜度-->
有了上面的案例,我們要做一個(gè)有內(nèi)涵的程序猿,空間復(fù)雜度絕不是一個(gè)程序占用了多少bytes的空間!
空間復(fù)雜度是用來衡量一個(gè)算法所需的額外空間!我們早期的計(jì)算機(jī)容量很小,在那個(gè)時(shí)候?qū)臻g復(fù)雜可謂是很在乎,但是現(xiàn)在隨著計(jì)算機(jī)的發(fā)展,現(xiàn)在我們都是在用空間換時(shí)間,所以我們?nèi)缃褚呀?jīng)不需要再特別關(guān)注一個(gè)算法的空間復(fù)雜度!
簡單做個(gè)總結(jié):時(shí)間復(fù)雜度算的是基本操作的執(zhí)行次數(shù),空間復(fù)雜度算的是變量的個(gè)數(shù)!
有的小伙伴看到這蠻開心,懂了。 但是不著急,我們下面來看如何計(jì)算常見的空間復(fù)雜度和時(shí)間復(fù)雜度!
如何計(jì)算時(shí)間復(fù)雜度和空間復(fù)雜度
我們直接上代碼!
// 請計(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的,所以會執(zhí)行10次,由此可見 F(N) = N² + 2 * N + 10
但是實(shí)際中我們計(jì)算時(shí)間復(fù)雜度時(shí),我們并不需要計(jì)算準(zhǔn)確的執(zhí)行次數(shù),只需要大概執(zhí)行次數(shù),這里我們用大O的漸進(jìn)表示法。
大O符號(Big O notation):是用于描述函數(shù)漸進(jìn)行為的數(shù)學(xué)符號。
推導(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階。
通過上面我們會發(fā)現(xiàn)大O的漸進(jìn)表示法去掉了那些對結(jié)果影響不大的項(xiàng),簡潔明了的表示出了執(zhí)行次數(shù)。
使用大O的漸進(jìn)表示法以后,F(xiàn)unc1的時(shí)間復(fù)雜度為:O(N²)
另外有些算法的時(shí)間復(fù)雜度存在最好、平均和最壞情況:
比如:在一個(gè)長度為N數(shù)組中搜索一個(gè)數(shù)據(jù) x
最好情況:一次找到
最壞情況:N次找到
平均情況:N/2次找到
我們在實(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ù)雜度對比的圖:
如何計(jì)算時(shí)間復(fù)雜度和空間復(fù)雜度
相信看完上邊的小伙伴們已經(jīng)按耐不住想要寫代碼了,接下來我們來看兩道有復(fù)雜度要求的算法題練習(xí)題,相信你聽我分析完會豎起大拇指說:妙??!
話不多說直接上題目?。?!
題目1:數(shù)組nums
包含從0
到n
的所有整數(shù),但其中缺了一個(gè)。請編寫代碼找出那個(gè)缺失的整數(shù)。你有辦法在O(n)時(shí)間內(nè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ù)加起來結(jié)果是ret1,再把數(shù)組中的數(shù)加起來是ret2,ret1-ret2就是我們要找的數(shù)!
思路3:異或 - 數(shù)組中的數(shù)依次跟0~N的有所數(shù)異或,最后剩下的數(shù)據(jù)就是缺的那個(gè)數(shù)字!
最后我們來實(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; }
看到這先別說妙,我們接著看下一道題!
題目2:給你一個(gè)數(shù)組,將數(shù)組中的元素向右輪轉(zhuǎn) k
個(gè)位置,其中 k
是非負(fù)數(shù)。
你可以使用空間復(fù)雜度為 O(1)
的 原地 算法解決這個(gè)問題嗎?
輸入: 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]
題目來源:189. 輪轉(zhuǎn)數(shù)組 - 力扣(LeetCode) (leetcode-cn.com)
思路1: 旋轉(zhuǎn)k次,先把數(shù)組nums最后一個(gè)元素放到一個(gè)臨時(shí)變量tmp,然后從倒數(shù)第二個(gè)元素往后移動,再把 tmp 存的最后一個(gè)元素的值賦給數(shù)組nums[0]。缺陷:效率低,時(shí)間復(fù)雜度為O(N*K)
思路2:用空間換時(shí)間,開辟一個(gè)跟nums一樣大的數(shù)組出來,先把后k個(gè)放到新數(shù)組,再把前k個(gè)接著放入新數(shù)組,時(shí)間復(fù)雜度為O(N),但是空間復(fù)雜度為O(N),不符合題意!
思路3:后k個(gè)逆置,前n-k個(gè)逆置,再整體逆置!
最后我們來實(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é)撒花?。。?!
動動發(fā)財(cái)?shù)男∈?,留個(gè)關(guān)注留個(gè)贊,我們快樂編程不頭禿。
gitee(碼云):Mercury. (zzwlwp) - Gitee.com
到此這篇關(guān)于C++ 超詳細(xì)分析數(shù)據(jù)結(jié)構(gòu)中的時(shí)間復(fù)雜度的文章就介紹到這了,更多相關(guān)C++ 時(shí)間復(fù)雜度內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
C語言結(jié)構(gòu)體版學(xué)生成績管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C語言結(jié)構(gòu)體版的學(xué)生成績管理系統(tǒng),文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2020-02-02C++ 使用CRC32檢測內(nèi)存映像完整性的實(shí)現(xiàn)步驟
當(dāng)我們使用動態(tài)補(bǔ)丁的時(shí)候,那么內(nèi)存中同樣不存在校驗(yàn)效果,也就無法抵御對方動態(tài)修改機(jī)器碼了,為了防止解密者直接對內(nèi)存打補(bǔ)丁,我們需要在硬盤校驗(yàn)的基礎(chǔ)上,增加內(nèi)存校驗(yàn),防止動態(tài)補(bǔ)丁的運(yùn)用。2021-06-06c++?qt自定義搜索編輯框的實(shí)現(xiàn)方法
這篇文章主要介紹了c++?qt自定義搜索編輯框,通過自定義QLineEdit,在編輯框里添加布局,將按鈕設(shè)置在右邊,當(dāng)點(diǎn)擊按鈕搜索按鈕時(shí)發(fā)送信號到主界面做相應(yīng)的操作,需要的朋友可以參考下2022-03-03C++實(shí)現(xiàn)LeetCode(89.格雷碼)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(89.格雷碼),本篇文章通過簡要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07