一個算法的好壞如何評價

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

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

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

這個算法還需要足夠健壯，即當輸入的數據非法或不合理時，也能適當的做出正確的反應或進行相應的處理

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

也就是所謂的時間復雜度和空間復雜度

   1.時間復雜度

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

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

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

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

是用于描述函數漸進行為的數學符號.

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

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

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

   4.時間復雜度的:最優、平均、最差情況，為什么時間復雜度看的是最差情況？

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

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

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

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

   6.什么是空間復雜度？

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

   7.如何求空間復雜度？ 普通函數&遞歸函數

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

   8. 分析遞歸斐波那契數列的：時間、空間復雜度，并對其進行優化，偽遞歸優化—>循環優化

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

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

   計算并根據O漸進表示法得出時間復雜度.

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

偽遞歸優化:

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);
}

時間復雜度:
   O(N);
   遞歸深度乘以每次遞歸的循環次數
   空間復雜度:
   O(1)或O(N)
   關鍵看編譯器是否優化,優化則為O(1)否則O(N);

循環優化:

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;
}

時間復雜度:O(N);

空間復雜度:O(1);

9.常見時間復雜度

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

undefined

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