健壯的演算法
❶ 健壯的演算法不會因非法的輸入數據而出現莫名其妙的狀態。是否正確,為什麼
正確啊,可以給出錯誤提示,但不能崩潰和給出錯誤答案。常見莫名奇妙問題就是答案錯誤,內存溢出,數組越界,野指針等等bug。比如做一個4則運算,如果不考慮除數不能為0,那麼程序就會崩潰
❷ 一個演算法的評價主要從哪些方面來考慮
一個演算法的評價主要從以下幾個方面來考慮:
1、時間復雜度
演算法的時間復雜度是指執行演算法所需要的計算工作量。一般來說,計算機演算法是問題規模n 的函數f(n),演算法的時間復雜度也因此記做。
T(n)=Ο(f(n))
因此,問題的規模n 越大,演算法執行的時間的增長率與f(n) 的增長率正相關,稱作漸進時間復雜度(Asymptotic Time Complexity)。
2、空間復雜度
演算法的空間復雜度是指演算法需要消耗的內存空間。其計算和表示方法與時間復雜度類似,一般都用復雜度的漸近性來表示。同時間復雜度相比,空間復雜度的分析要簡單得多。
3、正確性
演算法的正確性是評價一個演算法優劣的最重要的標准。
4、可讀性
演算法的可讀性是指一個演算法可供人們閱讀的容易程度。
5、健壯性
健壯性是指一個演算法對不合理數據輸入的反應能力和處理能力,也稱為容錯性。
(2)健壯的演算法擴展閱讀:
演算法可大致分為基本演算法、數據結構的演算法、數論與代數演算法、計算幾何的演算法、圖論的演算法、動態規劃以及數值分析、加密演算法、排序演算法、檢索演算法、隨機化演算法、並行演算法,厄米變形模型,隨機森林演算法。
演算法可以宏泛的分為三類:
一、有限的,確定性演算法 這類演算法在有限的一段時間內終止。他們可能要花很長時間來執行指定的任務,但仍將在一定的時間內終止。這類演算法得出的結果常取決於輸入值。
二、有限的,非確定演算法 這類演算法在有限的時間內終止。然而,對於一個(或一些)給定的數值,演算法的結果並不是唯一的或確定的。
三、無限的演算法 是那些由於沒有定義終止定義條件,或定義的條件無法由輸入的數據滿足而不終止運行的演算法。通常,無限演算法的產生是由於未能確定的定義終止條件。
❸ 如何才能設計出優秀的演算法
數據結構中評價一個好的演算法,應該從四個方面來考慮,分別是:
一、演算法的正確性。
二、演算法的易讀性。
三、是演算法的健壯性。
四、是演算法的時空效率(運行)。
演算法的設計取決於數據(邏輯)結構,演算法的實現取決於所採用的存儲結構。數據的存儲結構本質上是其邏輯結構在計算機存儲器中的實現。為了充分反映數據的邏輯結構,它在內存中的映像包括兩個方面,即數據元素之間的信息和數據元素之間的關系。不同的數據結構有相應的操作。數據操作是定義在數據邏輯結構上的操作演算法,如檢索、插入、刪除、更新和排序。
(3)健壯的演算法擴展閱讀
該演算法的一般性質包括:
1、對於任何符合輸入類型的輸入數據,都可以根據演算法來解決問題,軟體包保證了計算結構的正確性。
2、演算法中的每一條指令都必須能夠被人或機器執行。
3、確定性演算法應該在每一步之後都有明確的下一步指示。也就是說,確保每個步驟都有下一步行動的指示,並且不缺乏或只有模糊的下一步行動指示。
4、有限演算法的執行必須以有限的步數結束。
❹ 演算法的評價指標有哪些
時間復雜度和空間復雜度。
1、時間復雜度
演算法的時間復雜度是指執行演算法所需要的計算工作量。一般來說,計算機演算法是問題規模n 的函數f(n),演算法的時間復雜度也因此記做。
T(n)=Ο(f(n))
因此,問題的規模n 越大,演算法執行的時間的增長率與f(n) 的增長率正相關,稱作漸進時間復雜度(Asymptotic Time Complexity)。
2、空間復雜度
演算法的空間復雜度是指演算法需要消耗的內存空間。其計算和表示方法與時間復雜度類似,一般都用復雜度的漸近性來表示。同時間復雜度相比,空間復雜度的分析要簡單得多。
空間復雜度記做S(n)=O(f(n))。比如直接插入排序的時間復雜度是O(n^2),空間復雜度是O(1) 。而一般的遞歸演算法就要有O(n)的空間復雜度了,因為每次遞歸都要存儲返回信息。一個演算法的優劣主要從演算法的執行時間和所需要佔用的存儲空間兩個方面衡量。
(4)健壯的演算法擴展閱讀:
演算法的方法:
1、遞推法
遞推是序列計算機中的一種常用演算法。它是按照一定的規律來計算序列中的每個項,通常是通過計算機前面的一些項來得出序列中的指定項的值。其思想是把一個復雜的龐大的計算過程轉化為簡單過程的多次重復,該演算法利用了計算機速度快和不知疲倦的機器特點。
2、遞歸法
程序調用自身的編程技巧稱為遞歸(recursion)。一個過程或函數在其定義或說明中有直接或間接調用自身的一種方法,它通常把一個大型復雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解,遞歸策略只需少量的程序就可描述出解題過程所需要的多次重復計算,大大地減少了程序的代碼量。遞歸的能力在於用有限的語句來定義對象的無限集合。
一般來說,遞歸需要有邊界條件、遞歸前進段和遞歸返回段。當邊界條件不滿足時,遞歸前進;當邊界條件滿足時,遞歸返回。
注意:
(1) 遞歸就是在過程或函數里調用自身.
(2) 在使用遞歸策略時,必須有一個明確的遞歸結束條件,稱為遞歸出口。
❺ 演算法及其特性有哪些
1.演算法的重要特性(1)有窮性:一個演算法必須在執行有窮步驟之後正常結束,而不能形成無窮循環。
(2)確定性:演算法中的每一條指令必須有確切的含義,不能產生多義性。
(2)可行性:演算法中的每一條指令必須是切實可執行的,即原則上可以通過已經實現的基本運算執行有限次來實現。
(4)輸入:一個演算法應該有零個或多個輸入。
(5)輸出:一個演算法應該有一個或多個輸出,這些輸出是同輸入有特定關系的量。
2.演算法描述的方法(1)框圖描述:該方法使用流程圖或N-S圖來描述演算法。
(2)自然語言描述:該方法採用自然語言,同時添加高級程序設計語言如while、for和if等基本控制語句來描述演算法。這類描述方法自然、簡潔,但缺乏嚴謹性和結構性。
(2)類語言描述:這是介於程序設計語言和自然語言之間演算法描述形式,其特徵是突出演算法設計的主體部分而有意忽略某些過於嚴格的語法細節,如類C或C++的偽語言。這種演算法不能直接在計算機上運行,但專業設計人員經常使用它來描述演算法,它具有容易編寫、閱讀和格式統一的特點。
(4)程序設計語言描述:採用某種高級程序設計語言(如C或C++)來描述。這是可以在計算機上運行並獲得結果的演算法描述。
本課程將採用偽C語言進行演算法描述。
2.演算法與程序的關系演算法的含義與程序十分相似,但二者是有區別的。演算法和程序都是用來表達解決問題的邏輯步驟;演算法是對解決問題方法的具體描述,程序是演算法在計算機中的具體實現;一個程序不一定滿足有窮性(死循環),而演算法一定滿足有窮性;程序中的指令必須是機器可執行的,而演算法中的指令則無此限制;一個演算法若用計算機語言來書寫,則它就可以是一個程序。因此,程序是演算法,但演算法不一定是程序。4.演算法設計要求在演算法設計中,對同一個問題可以設計出不同的求解演算法。如何評價這些演算法的優劣,從而為演算法設計和選擇提供可靠的依據?通常可從以下四個方面評價演算法的質量:
(1)正確性:演算法應該能夠正確地執行預先規定的功能,並達到所期望的性能要求。
(2)可讀性:演算法應該好讀,以有利於讀者對程序的理解,便於調試和修改。
(2)健壯性:演算法應具有容錯處理。當輸入非法數據時,演算法應對其作出反應,而不是產生莫名其妙的輸出結果。
(4)效率與低存儲量需求:效率指的是演算法執行的時間。對於同一個問題,如果有多種演算法可以求解,執行時間短的演算法效率高。演算法存儲量指的是演算法執行過程中所需要的最大存儲空間。高效率和低存儲量這兩者與問題的規模有關。
❻ 演算法有五個方面的重要特徵,包括輸入,確定性,輸出,能行性還有
演算法有五個方面的重要特徵包括有窮性、確切性、輸入項、輸出項、可行性。
1、有窮性(Finiteness)
演算法的有窮性是指演算法必須能在執行有限個步驟之後終止;
2、確切性(Definiteness)
演算法的每一步驟必須有確切的定義;
3、輸入項(Input)
一個演算法有0個或多個輸入,以刻畫運算對象的初始情況,所謂0個輸入是指演算法本身定出了初始條件;
4、輸出項(Output)
一個演算法有一個或多個輸出,以反映對輸入數據加工後的結果。沒有輸出的演算法是毫無意義的;
5、可行性(Effectiveness)
演算法中執行的任何計算步驟都是可以被分解為基本的可執行的操作步驟,即每個計算步驟都可以在有限時間內完成(也稱之為有效性)。
(6)健壯的演算法擴展閱讀
1、迪傑斯特拉演算法(又譯戴克斯特拉演算法)
這種圖搜索演算法具有多種應用方式,能夠將需要解決的問題建模為圖,並在其中找到兩個節點間的最短路徑。
2、RSA 演算法
該演算法由 RSA 公司的創始人們開發而成,使得密碼學成果得以供世界上的每個人隨意使用,甚至最終塑造了當今密碼學技術的實現方式。
3、安全哈希演算法
這實際上並不是真正的演算法,而是由 NIST(美國國家標准技術研究所)所開發的一系列加密散列函數。然而,該演算法家族對於世界秩序的維持起到了至關重要的作用。
4、比例微積分演算法
該演算法旨在利用控制迴路反饋機制以最大程度控制期望輸出信號與實際輸出信號間的誤差。其適用於一切存在信號處理需求的場景,包括以自動化方式通過電子技術控制的機械、液壓或者熱力系統。
5、數據壓縮演算法
很難確定哪種壓縮演算法的重要性最高,因為根據實際應用需求,大家使用的演算法可能包括 zip、mp3 乃至 JPEG 以及 MPEG-2 等等。