時間復(fù)雜度與空間復(fù)雜度詳解

• （一）時間復(fù)雜度和空間復(fù)雜度的作用？
• （二）時間復(fù)雜度和空間復(fù)雜度如何計算？
• • （1）時間復(fù)雜度
  • • 具體案例分析
    • 時間復(fù)雜度的比較
  • （2）空間復(fù)雜度
  • • 兩種常見空間復(fù)雜度

企業(yè)建站必須是能夠以充分展現(xiàn)企業(yè)形象為主要目的，是企業(yè)文化與產(chǎn)品對外擴(kuò)展宣傳的重要窗口，一個合格的網(wǎng)站不僅僅能為公司帶來巨大的互聯(lián)網(wǎng)上的收集和信息發(fā)布平臺，創(chuàng)新互聯(lián)公司面向各種領(lǐng)域：玻璃鋼坐凳等網(wǎng)站設(shè)計、成都全網(wǎng)營銷推廣解決方案、網(wǎng)站設(shè)計等建站排名服務(wù)。
（一）時間復(fù)雜度和空間復(fù)雜度的作用？

答：度量算法的效率

1. 時間復(fù)雜度：用來衡量執(zhí)行算法所花費(fèi)的時間；
2. 空間復(fù)雜度：用來衡量執(zhí)行算法所占用的空間；

（二）時間復(fù)雜度和空間復(fù)雜度如何計算？ （1）時間復(fù)雜度

頻度：一個語句的頻度是指該語句在算法中被執(zhí)行的次數(shù)。

時間復(fù)雜度，即分析算法中所有語句的頻度之和T(n)的數(shù)量級。
因?yàn)樗惴ㄖ凶钌顚友h(huán)內(nèi)的語句的頻度與T(n)同量級，因此通常采用算法中最深層循環(huán)內(nèi)語句的頻度f(n)來分析算法的時間復(fù)雜度。將其記作： T ( n ) = O ( f ( n ) ) T(n)=O(f(n)) T(n)=O(f(n))

注意： 在實(shí)際計算中，一般取f(n)中隨n增長最快的項(xiàng)，將其系數(shù)置為1作為時間復(fù)雜度的度量。
例如：f(n)=an3+bn2+cn 的時間復(fù)雜度為 O(n3)；f(n)=5 的時間復(fù)雜度為O(1)

具體案例分析

1. 類型一：

void func(n){int i,j;
	for(i=0;ifor(j=i;j	printf("每天進(jìn)步一點(diǎn)點(diǎn)");
		}
	}
}

分析：
① 找最深層循環(huán)內(nèi)的語句的頻度，即printf("每天進(jìn)步一點(diǎn)點(diǎn)");的執(zhí)行次數(shù)；

• 當(dāng) i=0 時—— j 對應(yīng)深層循環(huán)執(zhí)行 n 次
• 當(dāng) i=1 時—— j 對應(yīng)深層循環(huán)執(zhí)行 n-1 次
• …
• 當(dāng) i=n-1 時—— j 對應(yīng)深層循環(huán)執(zhí)行 1 次
• 則最深層循環(huán)語句執(zhí)行次數(shù)為： n ( n + 1 ) 2 \frac{n(n+1)}{2} 2n(n+1)?

② 取f(n)中隨n增長最快的項(xiàng)，將其系數(shù)置1，即該函數(shù)的時間復(fù)雜度為 O(n2) 。

2. 類型二：

void func(n){int i;
	for(i=1;iprintf("每天進(jìn)步一點(diǎn)點(diǎn)");
	}
}

分析：
① 找最深層循環(huán)內(nèi)的語句的頻度，即printf("每天進(jìn)步一點(diǎn)點(diǎn)");的執(zhí)行次數(shù)；

• 當(dāng)循環(huán)內(nèi)語句執(zhí)行次數(shù)為 1 時—— i=1
• 當(dāng)循環(huán)內(nèi)語句執(zhí)行次數(shù)為 2 時—— i=2
• 當(dāng)循環(huán)內(nèi)語句執(zhí)行次數(shù)為 3 時—— i=22
• …
• 當(dāng)循環(huán)內(nèi)語句執(zhí)行次數(shù)為 k 時—— i= 2 k ? 1 2^{k-1} 2k?1
• 則如果當(dāng) i= 2 k 2^{k} 2k 時不滿足條件 i

② 取f(n)中隨n增長最快的項(xiàng)，將其系數(shù)置1，即該函數(shù)的時間復(fù)雜度為 O( l o g 2 n log_2n log2?n) 。

時間復(fù)雜度的比較

O(1)常數(shù)階< O(logn)對數(shù)階< O(n)線性階< O(n2)平方階< O(n3)(立方階)< O( 2 n 2^n 2n) (指數(shù)階)

（2）空間復(fù)雜度

一個程序在執(zhí)行時所需空間包括：存儲本身所用的指令、常數(shù)、變量和輸入數(shù)據(jù)的空間，以及對數(shù)據(jù)進(jìn)行操作處理所申請使用的輔助空間等。

空間復(fù)雜度，使用S(n)來定義算法所耗費(fèi)的存儲空間，記作 S ( n ) = O ( g ( n ) ) S(n)=O(g(n)) S(n)=O(g(n))

兩種常見空間復(fù)雜度

1. 如果算法執(zhí)行所需要的臨時空間不隨著某個變量n的大小而變化，即此算法空間復(fù)雜度為一個常量，可表示為 O(1)。例如：

void func(n){int i=1;
 int j=2;
 int k=i+j;//算法空間與n無關(guān)
}

2. 如果隨著輸入值 n 的增大，程序申請的臨時空間也隨之變化，則程序的空間復(fù)雜度需要具體分析，例如：

void func(n){int a[n];//所申請的空間隨著n的取值而進(jìn)行線性變化，空間復(fù)雜度為O(n)
}

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)站題目：數(shù)據(jù)結(jié)構(gòu)：時間復(fù)雜度和空間復(fù)雜度求解思路方法詳解-創(chuàng)新互聯(lián)
URL鏈接：http://chinadenli.net/article18/dgjdgp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供小程序開發(fā)、做網(wǎng)站、網(wǎng)站改版、云服務(wù)器、App設(shè)計、企業(yè)建站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)