創(chuàng)新互聯(lián)www.cdcxhl.cn八線動(dòng)態(tài)BGP香港云服務(wù)器提供商，新人活動(dòng)買多久送多久，劃算不套路！

成都創(chuàng)新互聯(lián)-專業(yè)網(wǎng)站定制、快速模板網(wǎng)站建設(shè)、高性價(jià)比梁河網(wǎng)站開發(fā)、企業(yè)建站全套包干低至880元,成熟完善的模板庫(kù),直接使用。一站式梁河網(wǎng)站制作公司更省心,省錢,快速模板網(wǎng)站建設(shè)找我們，業(yè)務(wù)覆蓋梁河地區(qū)。費(fèi)用合理售后完善，十載實(shí)體公司更值得信賴。

一個(gè)算法的好壞如何評(píng)價(jià)？很多新手對(duì)此不是很清楚，為了幫助大家解決這個(gè)難題，下面小編將為大家詳細(xì)講解，有這方面需求的人可以來(lái)學(xué)習(xí)下，希望你能有所收獲。

首先，這個(gè)算法必須是正確的

其次，好的算法應(yīng)該是友好的，便于人們理解和交流，并且是機(jī)器可執(zhí)行的。

這個(gè)算法還需要足夠健壯，即當(dāng)輸入的數(shù)據(jù)非法或不合理時(shí)，也能適當(dāng)?shù)淖龀稣_的反應(yīng)或進(jìn)行相應(yīng)的處理

最后它還必須擁有高效率和低存儲(chǔ)量要求。

也就是所謂的時(shí)間復(fù)雜度和空間復(fù)雜度

   1.時(shí)間復(fù)雜度

定義:在計(jì)算機(jī)科學(xué)中,算法的時(shí)間復(fù)雜度是一個(gè)函數(shù),他定量描述了該算法的運(yùn)行時(shí)間.一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間,從理論上講,只有你把你的程序放機(jī)器上跑起來(lái),才能知道.然而我們有一套時(shí)間復(fù)雜度的分析方式.一個(gè)算法所花費(fèi)的時(shí)間與其中語(yǔ)句的執(zhí)行次數(shù)成正比例.算法中的基本操作的執(zhí)行次數(shù),為算法的時(shí)間復(fù)雜度.

   2.時(shí)間復(fù)雜度為什么不使用時(shí)間來(lái)衡量而使用基本語(yǔ)句的運(yùn)行次數(shù)來(lái)衡量？

算法的執(zhí)行時(shí)間依賴于具體的軟硬件環(huán)境，所以，不能用執(zhí)行時(shí)間的長(zhǎng)短來(lái)衡量算法的時(shí)間復(fù)雜度，而要通過(guò)基本語(yǔ)句執(zhí)行次數(shù)的數(shù)量級(jí)來(lái)衡量。

   3.時(shí)間復(fù)雜度的O漸進(jìn)表示法 (Big O notation)

是用于描述函數(shù)漸進(jìn)行為的數(shù)學(xué)符號(hào).

大O階方法推導(dǎo):
   計(jì)算基本語(yǔ)句的執(zhí)行次數(shù)的數(shù)量級(jí)；　
   只需計(jì)算基本語(yǔ)句執(zhí)行次數(shù)的數(shù)量級(jí)，這就意味著只要保證基本語(yǔ)句執(zhí)行次數(shù)的函數(shù)中的最高次冪正確即可，可以忽略所有低次冪和最高次冪的系數(shù)。這樣能夠簡(jiǎn)化算法分析，并且使注意力集中在最重要的一點(diǎn)上：增長(zhǎng)率。
　如果算法中包含嵌套的循環(huán)，則基本語(yǔ)句通常是最內(nèi)層的循環(huán)體，如果算法中包含并列的循環(huán)，則將并列循環(huán)的時(shí)間復(fù)雜度相加。例如：

　for (i=1; i<=n; i++)
　　x++;　　
　　for (i=1; i<=n; i++)
　　for (j=1; j<=n; j++)
　　x++;　

第一個(gè)for循環(huán)的時(shí)間復(fù)雜度為Ο(n)，第二個(gè)for循環(huán)的時(shí)間復(fù)雜度為Ο(n2)，則整個(gè)算法的時(shí)間復(fù)雜度為Ο(n+n2)=Ο(n2)。

   4.時(shí)間復(fù)雜度的:最優(yōu)、平均、最差情況，為什么時(shí)間復(fù)雜度看的是最差情況？

最差情況下的復(fù)雜度是所有可能的輸入數(shù)據(jù)所消耗的大資源，如果最差情況下的復(fù)雜度符合我們的要求，我們就可以保證所有的情況下都不會(huì)有問題。

某些算法經(jīng)常遇到最差情況。比如一個(gè)查找算法，經(jīng)常需要查找一個(gè)不存在的值。
   也許你覺得平均情況下的復(fù)雜度更吸引你，可是平均情況也有幾點(diǎn)問題。第一，難計(jì)算，多數(shù)算法的最差情況下的復(fù)雜度要比平均情況下的容易計(jì)算的多，第二，有很多算法的平均情況和最差情況的復(fù)雜度是一樣的. 第三，什么才是真正的平均情況？如果你假設(shè)所有可能的輸入數(shù)據(jù)出現(xiàn)的概率是一樣的話，也是不合理的。其實(shí)多數(shù)情況是不一樣的。而且輸入數(shù)據(jù)的分布函數(shù)很可能是你沒法知道。
考慮最好情況的復(fù)雜度更是沒有意義。

   5.如何求解：二分查找、遞歸求階乘、遞歸斐波那契的時(shí)間復(fù)雜度？

二分查找:通過(guò)折紙查找求解時(shí)間復(fù)雜度為O(logN);
   遞歸求階乘:數(shù)基本操作遞歸N次得到時(shí)間復(fù)雜度為O(N);
   遞歸斐波那契:分析得出基本操作遞歸了2^{N次,時(shí)間復(fù)雜度為O(2}N);

   6.什么是空間復(fù)雜度？

空間復(fù)雜度是對(duì)一個(gè)算法在運(yùn)行過(guò)程中臨時(shí)占用存儲(chǔ)空間大小的度量.空間復(fù)雜度不是程序占用了多少bytes的空間,因?yàn)檫@個(gè)也沒太大意義,所以空間復(fù)雜度算的是變量的個(gè)數(shù).空間復(fù)雜度計(jì)算規(guī)則基本跟時(shí)間復(fù)雜度類似,也使用大O漸進(jìn)法表示.

   7.如何求空間復(fù)雜度？ 普通函數(shù)&遞歸函數(shù)

一個(gè)算法的空間復(fù)雜度只考慮在運(yùn)行過(guò)程中為局部變量分配的存儲(chǔ)空間的大小，它包括為參數(shù)表中形參變量分配的存儲(chǔ)空間和為在函數(shù)體中定義的局部變量分配的存儲(chǔ)空間兩個(gè)部分。若一個(gè)算法為 遞歸算法，其空間復(fù)雜度為遞歸所使用的堆?？臻g的大小，它等于一次調(diào)用所分配的臨時(shí)存儲(chǔ)空間的大小乘以被調(diào)用的次數(shù)(即為遞歸調(diào)用的次數(shù)加1，這個(gè)1表示開始進(jìn)行的一次非遞歸調(diào)用)。算法的空間復(fù)雜度一般也以數(shù)量級(jí)的形式給出。如當(dāng)一個(gè)算法的空間復(fù)雜度為一個(gè)常量，即不隨被處理數(shù)據(jù)量n的大小而改變時(shí)，可表示為O(1)；當(dāng)一個(gè)算法的空間復(fù)雜度與以2為底的n的對(duì)數(shù)成正比時(shí)，可表示為O(log2n)；當(dāng)一個(gè)算法的空間復(fù)雜度與n成線性比例關(guān)系時(shí)，可表示為O(n).若形參為數(shù)組，則只需要為它分配一個(gè)存儲(chǔ)由實(shí)參傳送來(lái)的一個(gè)地址指針的空間，即一個(gè)機(jī)器字長(zhǎng)空間；若形參為引用方式，則也只需要為其分配存儲(chǔ)一個(gè)地址的空間，用它來(lái)存儲(chǔ)對(duì)應(yīng)實(shí)參變量的地址，以便由系統(tǒng)自動(dòng)引用實(shí)參變量。

   8. 分析遞歸斐波那契數(shù)列的：時(shí)間、空間復(fù)雜度，并對(duì)其進(jìn)行優(yōu)化，偽遞歸優(yōu)化—>循環(huán)優(yōu)化

long long Fib(int N) {
	if (N < 3)
		return 1;
	return Fib(N - 1) + Fib(N - 2);
}

普通遞歸實(shí)現(xiàn)的斐波那契數(shù)列:
   時(shí)間復(fù)雜度:O(2^n)

   計(jì)算并根據(jù)O漸進(jìn)表示法得出時(shí)間復(fù)雜度.

空間復(fù)雜度:O(N);遞歸深度乘以(每一次遞歸的空間占用{有輔助空間或常量})

偽遞歸優(yōu)化:

long long fib (long long first, longlong second, int N) {
	if(N <3)
	return 1;
	if(N == 3)
	return first + second;
	return fib(second, first+second,N-1);
}

時(shí)間復(fù)雜度:
   O(N);
   遞歸深度乘以每次遞歸的循環(huán)次數(shù)
   空間復(fù)雜度:
   O(1)或O(N)
   關(guān)鍵看編譯器是否優(yōu)化,優(yōu)化則為O(1)否則O(N);

循環(huán)優(yōu)化:

long long  Fib(int N) {
	long long first = 1;
	long long second = 1;
	long long ret = 0;
	
	for (int i = 3; i <= N ; ++i) {
		ret = first + second;
		first = second;
		second = ret;
	}
	return second;
}

時(shí)間復(fù)雜度:O(N);

空間復(fù)雜度:O(1);

9.常見時(shí)間復(fù)雜度

常見的算法時(shí)間復(fù)雜度由小到大依次為：　　Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!)　　Ο(1)表示基本語(yǔ)句的執(zhí)行次數(shù)是一個(gè)常數(shù)，一般來(lái)說(shuō)，只要算法中不存在循環(huán)語(yǔ)句，其時(shí)間復(fù)雜度就是Ο(1)。Ο(log2n)、Ο(n)、Ο(nlog2n)、Ο(n2)和Ο(n3)稱為多項(xiàng)式時(shí)間，而Ο(2n)和Ο(n!)稱為指數(shù)時(shí)間。

undefined

看完上述內(nèi)容是否對(duì)您有幫助呢？如果還想對(duì)相關(guān)知識(shí)有進(jìn)一步的了解或閱讀更多相關(guān)文章，請(qǐng)關(guān)注創(chuàng)新互聯(lián)-成都網(wǎng)站建設(shè)公司行業(yè)資訊頻道，感謝您對(duì)創(chuàng)新互聯(lián)的支持。

網(wǎng)站題目：一個(gè)算法的好壞如何評(píng)價(jià)-創(chuàng)新互聯(lián)
當(dāng)前路徑：http://aaarwkj.com/article34/cocpse.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供搜索引擎優(yōu)化、網(wǎng)站內(nèi)鏈、營(yíng)銷型網(wǎng)站建設(shè)、品牌網(wǎng)站設(shè)計(jì)、微信公眾號(hào)、網(wǎng)頁(yè)設(shè)計(jì)公司

廣告

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