演算法好壞三條

Ⅰ 如何比較兩個演算法的好壞，有什麼指標

演算法是一個良定義的計算過程，以一個或多個值輸入，並以一個或多個值輸出。
評價演算法的好壞的因素：·演算法是正確的；
·執行演算法的時間；
·執行演算法的存儲空間（主要是輔助存儲空間）；
·演算法易於理解、編碼、調試。
**************************************************************************************************************
時間復雜度：是某個演算法的時間耗費，它是該演算法所求解問題規模n的函數。
漸近時間復雜度：是指當問題規模趨向無窮大時，該演算法時間復雜度的數量級。
評價一個演算法的時間性能時，主要標准就是演算法的漸近時間復雜度。
演算法中語句的頻度不僅與問題規模有關，還與輸入實例中各元素的取值相關。
時間復雜度按數量級遞增排列依次為：常數階O(1)、對數階O(log2n)、線性階O(n)、線性對數階O(nlog2n)、平方階O(n^2)、立方階O(n^3)、……k次方階O(n^k)、指數階O(2^n)。
空間復雜度：是某個演算法的空間耗費，它是該演算法所求解問題規模n的函數。
演算法的時間復雜度和空間復雜度合稱演算法復雜度。

Ⅱ 評價一個演算法性能好壞的重要標準是

1、時間復雜度

演算法的時間復雜度是指執行演算法所需要的計算工作量。一般來說，計算機演算法是問題規模n 的函數f(n)，演算法的時間復雜度也因此記做寬咐。

3、正確性

演算法的正滾旦確性是評價一個演算法優劣的最重要的標准。

4、可讀性

演算法的可讀性是指一個演算法可供人們閱讀的容易程度。

5、健壯性

健壯性是指一個演算法對不合理數據輸大巧擾入的反應能力和處理能力，也稱為容錯性。

Ⅲ 如何評價一個演算法的好壞

首先，這個演算法必須是正確的
其次，好的演算法應該是友好的，便於人們理解和交流，並且是機器可執行的。
這個演算法還需要足夠健壯，即當輸入的數據非法或不合理時，也能適當的做出正確的反應或進行相應的處理
最後它還必須擁有高效率和低存儲量要求。
也就是所謂的時間復雜度和空間復雜度

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);
遞歸斐波那契:分析得出基本操作遞歸了2N次,時間復雜度為O(2N);

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!)稱為指數時間。

Ⅳ 演算法分析：如何分析一個演算法的效率好壞

當我們說演算法分析的時候我們在說什麼？（狹義的技術層面的定義）：
演算法分析指的是： 對演算法在運行時間和存儲空間這兩種資源的利用效率進行研究 。
即時間效率和空間效率。

時間效率指演算法運行有多快；
空間效率指演算法運行時需要多少額外的存儲空間。
（時間效率也叫時間復雜度；空間效率也叫空間復雜度。）

在計算機時代早期，時間和空間這兩種資源都是及其昂貴的。但經過半個多世紀的發展，計算機的速度和存儲容量都已經提升了好幾個數量級。
現在空間效率已經不是我們關注的重點了，但時間效率的重要性並沒有減弱到這種可以忽略的程度。

所以，當我們分析一個演算法的的時候，我們只關注它的時間效率 。

當我們遇到一個演算法時，我們可以用這樣一個通用的思路去分析它：

首先第一卜伍知步考慮這個演算法的輸入規模是什麼？即輸入參數，再換句話說也就是待解決的問題有多大？
從這里入手是因為一個顯而易見的規律就是，不管使用什麼演算法， 輸入規模越大，運行效率肯定會更長 。
輸入規模的確定要根據具體要解決的實際問題的細節來決定，相同的問題不同的細節，輸入規模是不一樣的。比如：一個拼寫檢查的演算法，
如果演算法關注的是單獨的字元檢查，那麼字元的數量就是輸入規模的大小；
如果演算法關注的是片語搭配的檢查，那麼這個輸入規模就要比單獨的字元檢查的輸入規模要小，這里輸入規模就是詞的數量了。

接下來第二步考慮這個演算法的運行時間，即這個演算法運行地快慢。
我們可以簡單地用計時的方法，即某個演算法運行了多少毫秒。
但這個方式有一個缺陷就是在不同計算機上，相同演算法的運行時間是不一樣，因為有的電腦快有的電腦慢。
所以有沒有一種度量方法可以排除這些無關因素？
答案是肯定的，我們可以關注演算法執行了多少步，即 操作的運行次數 。而且為了簡化問題我們只需關注最重要的操作步驟，即所謂的 基本操作 ，因為基本操作已經足夠可以決定這個演算法的品質。
比如一個演算法通常是最內層的循環中是最費時的操作，那我們就只需要把它循環了多少次作為基本操作進行研究。

這里需要延伸的一點是在大規模的輸入情況下考慮執行次數的增長次數。因為針對小規模的輸入，在運行時間的差別上不太明顯。比如只對100個數字進行排序，不管你用什麼排序演算法，時間效率都差不多。只有在輸入規模變大的時候，演算法的差異才變得既明顯又重要了起來。
簡單來說，
如果一個演算法在輸入規模變大時，但運行時間平緩增長，那麼我們就可以說它就是一個效率高的演算法；
而如果一個演算法在輸入規模變大時，它的運行時間成指數級增長，那就可以說這個演算法的效率很差。
總而言之就是，對基本操作的大規模輸入情況下的變化的研究才更具有深遠意義。

當我們了解了輸入規模對演算法時間效率的會產生影響，但演算法的執行效率卻不僅僅只受輸入規模的影響，某些情況下，演算法的執行效率更取決於輸入參數的細節。
比如：一個簡單的順序查找的演算法，在數組里查找數字 9：
在數組 l1 = [1, 2, 3, 4, 5, 6, 7, 8, 9 ] 里查找數字 9 和在相同的輸入規模的另一個數組 l2 = [ 9 , 1, 2, 3, 4, 5, 6, 7, 8]里查找數字 9，在數組 l2 的執行效率肯定更高。
上面小例子中的兩個數組就體現了兩個極端： 輸入最優情況 和 輸入最壞情況 。
相對應的，
在輸入最優情況下的演算法就叫 最優效率 ；
在輸入最壞情況下的演算法就叫 最差效率 ；
在這里有兩個經驗性的規則：

在現實情況下，輸入是「隨機」的，既不會是最優輸入也不會是最壞輸入。所以這里又型消要引出一個概念，即： 平均效率 。
首先指出，我們絕不能用「最優效率」和「最差效率」的平均數求得 平均效率 ，即便有時間這個平均數和真正的 平均效率 巧合地一致。
正確的步驟是：我們要對輸入規模 n 做一些假設。
對於上面的順序查找演算法的例子，標準的假設有兩個：

基於這兩個假設求平均效率可得：

由此，平均效率橘燃 C(n) = p(n+1) / 2 + n(1-p)

由此可知，

從這個例子可以發現，平均效率的研究要比最差效率和最優效率的研究困難很多：
我們要將輸入規模 n 劃分為幾種類型，對於同類型的輸入，使得演算法的執行次數是相同的。

演算法是計算機科學的基礎，以後會繼續更新演算法相關的隨筆，對演算法感興趣的朋友歡迎關注本博客，也歡迎大家留言討論。
我們正處於大數據時代，對數據處理感興趣的朋友歡迎查看另一個系列隨筆：
利用Python進行數據分析 基礎系列隨筆匯總

Introction to The Design and Analysis of Algorithms, Third Edition by Anany Leitin

Ⅳ 如何判斷演算法優劣

演算法的好壞是看它的運行效率比如遞歸一般來說是比較耗時間的，也就是說效率低當然也看具體情況，有的演算法在基數小的情況是差不多，性能反而還好點

Ⅵ 衡量演算法好壞的標准

1：時間復雜度：

可以簡單的說就是：大概程序要被執行的次數，而非時間。注意：是次數，不是時間，因為不同機器的性能是不一樣的,不要用計時器在那裡計時誰的更快。當然，如果在同一台電腦上運行計時另說。
Question：怎樣看待一個程序執行的速度是快還是慢？
Answer：要看他里邊最關鍵的運行次數最多的那一個步驟到底執行了幾次，用這個來衡量演算法的時間復雜度

2：空間復雜度：

同樣簡單來說就是：演算法執行過程中大概所佔用的最大的內存。

3：難易程度：

所研究的演算法盡可能讓大家能看懂。

4：健壯性：

簡單來說哦，不要一碰就完不結實

5：正確性：

一定要正確，感覺這一特性說不說都是可以，不正確也不能用，這一切的前提都是以正確為前提的。