一個算法的好壞如何評價

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

首先，這個算法必須是正確的

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

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

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

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

   1.時間復(fù)雜度

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

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

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

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

是用于描述函數(shù)漸進行為的數(shù)學(xué)符號.

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

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

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

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

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

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

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

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

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

空間復(fù)雜度是對一個算法在運行過程中臨時占用存儲空間大小的度量.空間復(fù)雜度不是程序占用了多少bytes的空間,因為這個也沒太大意義,所以空間復(fù)雜度算的是變量的個數(shù).空間復(fù)雜度計算規(guī)則基本跟時間復(fù)雜度類似,也使用大O漸進法表示.

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

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

   8. 分析遞歸斐波那契數(shù)列的：時間、空間復(fù)雜度，并對其進行優(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);
}

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

   計算并根據(jù)O漸進表示法得出時間復(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);
}

時間復(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;
}

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

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

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

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

undefined

看完上述內(nèi)容是否對您有幫助呢？如果還想對相關(guān)知識有進一步的了解或閱讀更多相關(guān)文章，請關(guān)注億速云行業(yè)資訊頻道，感謝您對億速云的支持。