設計算法

設計算法

對算法的學習包括5個方面:設計算法、表示算法、確認算法、分析算法、驗證算法。算法設計工作是不可能完全自動化的,應學習了解已經被實踐證明有用的一些基本的算法設計方法,這些基本的設計方法不僅適用於計算機科學,而且適用於電氣工程、運籌學等領域。設計算法的原則包括:正確性、可讀性、健壯性、高效率與低存儲量。

定義

算法就是為解決問題而採取的方法與步驟。隨著計算機的出現,算法被廣泛地套用於計算機的問題求解中,被認為是程式設計的精髓。對算法的學習包括5個方面:設計算法、表示算法、確認算法、分析算法、驗證算法。算法設計工作是不可能完全自動化的,應學習了解已經被實踐證明有用的一些基本的算法設計方法,這些基本的設計方法不僅適用於計算機科學,而且適用於電氣工程、運籌學等領域。

原則

對於一個特定問題的算法在大部分情況下都不是唯一的。也就是說,同一個問題,可以有多種解決問題的算法,而對於特定的問題、特定的約束條件,相對好的算法還是存在的。因此,在特定問題、特定的條件下,選擇合適的算法,會對解決問題有很大的幫助;否則前人的智慧我們不能借鑑,凡事就都得自己從頭研究了,這就是所謂的要去“發明輪子”。

在設計算法時,通常要考慮以下原則:

正確性

算法的正確性是指算法至少應該具有輸入、輸出和加工處理無歧義性、能正確反映問題的需要、能夠得到問題的正確答案。

但是算法的“正確”通常在用法上有很大的差別,大體分為以下4個層次:

(1)算法程式沒有語法錯誤;

(2)算法程式能夠根據正確的輸入的值得到滿足要求的輸出結果;

(3)算法程式能夠根據錯誤的輸出的值滿足規格說明的輸出結果;

(4)算法程式對於精心設計、極其刁難的測試數據都能滿足要求的輸出結果。

對於這4層含義,層次(1)要求最低,因為僅僅沒有語法錯誤實在談不上是好的算法。而層次(4)是最困難的,人們幾乎不可能逐一驗證所有的輸入都得到正確的結果。

因此,算法的正確性在大部分情況下都不可能用程式來證明,而是用數學方法證明的。證明一個複雜算法在所有層次上都是正確的,代價非常昂貴。所以一般情況下,人們把層次(3)作為一個算法是否正確的標準。

可讀性

設計算法的目的,一方面是為了讓計算機執行,但還有一個重要的目的就是為了便於他人的閱讀,讓人理解和交流,自己將來也可閱讀。如果可讀性不好,時間長了自己都不知道寫了什麼,可讀性是評判算法(也包括實現它的程式代碼)好壞很重要的標誌。可讀性不好不僅無助於人們理解算法,晦澀難懂的算法往往隱含錯誤,不易被發現並且難以調試和修改。

健壯性

當輸入的數據非法時,算法應當恰當地做出反應或進行相應處理,而不是莫名其妙的輸出結果。並且處理出錯的方法不應是中斷程式的執行,而應是返回一個表示錯誤或錯誤性質的值,以便於在更高的抽象層次上進行處理。

高效率與低存儲量

通常,算法的效率指的是算法的執行時間;算法的存儲量指的是算法執行過程中所需要的最大存儲空間,兩者的複雜度都與問題的規模有關。算法分析的任務是對設計的每一個具體的算法,利用數學工具,討論其複雜度,探討具體算法對問題的適應性。

在滿足以上幾點以後,還可以考慮對算法進程進一步最佳化,儘量滿足時間效率高和空間存儲量低的需求。

步驟

設計算法的一般過程可以歸納為以下幾個步驟:

建立數學模型

通過對問題進行詳細的分析,抽象出相應的數學模型。

確定數據結構與算法

確定使用的數據結構,並在此基礎上設計對此數據結構實施各種操作的算法。

選用語言

選用某種語言將算法轉化成程式。

調試並運行

調試並運行這些程式。

相關詞條

熱門詞條

聯絡我們