您好,登錄后才能下訂單哦!
本篇文章為大家展示了C語(yǔ)言中關(guān)于時(shí)間復(fù)雜度的示例分析,內(nèi)容簡(jiǎn)明扼要并且容易理解,絕對(duì)能使你眼前一亮,通過(guò)這篇文章的詳細(xì)介紹希望你能有所收獲。
空間效率,時(shí)間效率(較為關(guān)注)
時(shí)間復(fù)雜度:算法中的操作執(zhí)行次數(shù),為算法的時(shí)間復(fù)雜度。(不是具體時(shí)間,而是執(zhí)行次數(shù))
時(shí)間復(fù)雜度
(1)是一個(gè)估算,看表達(dá)式中影響大的那一項(xiàng),如N*N+2N+10中,N*N對(duì)整個(gè)式子影響最大,故其時(shí)間復(fù)雜度為N*N,用大O的漸近表示法O(N*N)。
(2)去掉時(shí)間表達(dá)式中的常數(shù)項(xiàng)乘積,例如,得到一個(gè)準(zhǔn)確的時(shí)間表達(dá)式為2N+10,則估算得到的時(shí)間復(fù)雜度為O(N)
(3)對(duì)于多個(gè)未知數(shù)時(shí),例如時(shí)間表達(dá)式為N+M,假設(shè)M,N差不多大,則O(M)或O(N);假設(shè)M遠(yuǎn)大于N,則O(M)。
(4)用常數(shù)1去替代所有確定的常數(shù),如準(zhǔn)確的時(shí)間表達(dá)式為100,O(1).
(5)未知數(shù)和常數(shù),濾去常數(shù)。
(6)另外有些算法分為最好,最壞,平均這三種情況。當(dāng)算法存在這三種情況時(shí),選最壞的時(shí)間復(fù)雜度,例如假設(shè)字符串長(zhǎng)度為N,“sdsfrsgtr...”,遍歷字符串,求S的時(shí)間復(fù)雜度,最好O(1),最壞O(N),平均O(N/2)。
A. 在冒泡排序中,
第一趟冒泡:N
第二趟冒泡:N-1
第三趟冒泡:N-2
第N趟冒泡:1
為等差數(shù)列,準(zhǔn)確次數(shù)為: N*(N+1)/2
故冒泡排序時(shí)間復(fù)雜度為O(N*N)
B. 在二分查找/折半查找中:
假設(shè)二分了X次,有1*2*2....*2=N,2^X=N, X=(log2) N
算法的復(fù)雜度計(jì)算中,喜歡省略成logN,因?yàn)椴缓脤懙讛?shù),但是寫成lg N,是錯(cuò)的。
C. 在某些階乘的運(yùn)算中求時(shí)間復(fù)雜度:
long long Factorial(size_t N) { return N<2 ? N:Factorial(N-1)*N; }
如Factorial(10),則返回factorial(9)*10,在返回到factorial(9)*8.....以此類推返回到
factorial(1)*2返回到1.(實(shí)際是10?。?strong>遞歸了N次,故時(shí)間復(fù)雜度為O(N)。(特別注意:結(jié)返回結(jié)果是N!,但是操作的次數(shù)是遞歸了N次,所以時(shí)間復(fù)雜度為O(N))
空間復(fù)雜度是算法運(yùn)行過(guò)程中臨時(shí)占用存儲(chǔ)空間大小的量度,不在意其具體占了多少比特的大小,而是計(jì)算變量的個(gè)數(shù)。
對(duì)照時(shí)間復(fù)雜度的計(jì)算方法。注意:時(shí)間是累積的,空間是不累計(jì)的,空間可以銷毀。
例題1:消失的數(shù)字
思路1:排序 0 1 2 3 4 5 6 7 9 一次比較,若下一個(gè)數(shù)與上一個(gè)數(shù)只差為1,則掠過(guò),若下一個(gè)數(shù)比上一個(gè)數(shù)>1,則找到,但時(shí)間復(fù)雜度不符合。
思路2:把0到N加到一起,結(jié)果ret1,再把數(shù)組中的數(shù)加到一起ret2,ret1-ret2就是要找的數(shù)。
思路3:異或:相同為0,相異為1。將數(shù)組中的數(shù)與0-N數(shù)互相異或,最后剩下的那個(gè)數(shù)字就是缺的那個(gè)數(shù)。
int missingNumber(int* nums, int numsSize){ int x=0; //先和數(shù)組的數(shù)進(jìn)行異或 for(int i=0;i<numsSize;++i) { x^=nums[i]; } //在和0-N的數(shù)進(jìn)行異或 for(int j=0;j<numsSize+1;++j) { x^=j; } return x; }
要注意0-N數(shù)異或時(shí),注意j<numsSize+1,它比原數(shù)組中元素個(gè)數(shù)多1。
例題2:旋轉(zhuǎn)數(shù)組
思路1:保存最后一個(gè)數(shù),將其挪到前面來(lái)。k次
void rotate(int* nums, int numsSize, int k){ for(int i=0;i<k;++i) { int tmp=nums[numsSize -1]; for(int end=numsSize -2;end >=0;--end) { nums[end+1]=nums[end]; } nums[0]=tmp; } }
但此時(shí)時(shí)間復(fù)雜度為O(N*K),跑不過(guò)~
思路2:以空間換時(shí)間,嘗試著多消耗一點(diǎn)空間,一次換成。將后K個(gè)保存,移到前面來(lái),直接得到。時(shí)間復(fù)雜度為O(N),空間復(fù)雜度為O(N)
思路3:后K個(gè)逆置,前K個(gè)逆置,整體逆置(這個(gè)實(shí)在是太牛了?。。?/p>
c代碼為:
//逆置 void Reverse(int *nums ,int left,int right){ while(left<right) { int tmp=nums[left]; nums[left]=nums[right]; nums[right]=tmp; ++left; --right; } } void rotate(int* nums, int numsSize, int k) { //控制好下標(biāo),后N-K個(gè) Reverse(nums,numsSize-k,numsSize-1); Reverse(nums,0,numsSize-k-1); Reverse(nums,0,numsSize-1); }
注意結(jié)果可能出錯(cuò):
此時(shí)需要注意K是否大于N,當(dāng)K>N時(shí)需要取模:k%=numsSize
添加:if(K>numsSize){ K%numsSize;}
//逆置 void Reverse(int *nums ,int left,int right){ while(left<right) { int tmp=nums[left]; nums[left]=nums[right]; nums[right]=tmp; ++left; --right; } } void rotate(int* nums, int numsSize, int k) { if(k>numsSize) { k%=numsSize; } //控制好下標(biāo),后N-K個(gè) Reverse(nums,numsSize-k,numsSize-1); Reverse(nums,0,numsSize-k-1); Reverse(nums,0,numsSize-1); }
在力扣上運(yùn)行得到:
上述內(nèi)容就是C語(yǔ)言中關(guān)于時(shí)間復(fù)雜度的示例分析,你們學(xué)到知識(shí)或技能了嗎?如果還想學(xué)到更多技能或者豐富自己的知識(shí)儲(chǔ)備,歡迎關(guān)注億速云行業(yè)資訊頻道。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。