淺談基于計(jì)算機(jī)算法設(shè)計(jì)及其評價標(biāo)準(zhǔn)分析

昝道廣 梁肖裕 劉忠青 徐西彤 李晨輝 山東科技大學(xué)電氣信息系

計(jì)算機(jī)通過執(zhí)行程序員設(shè)計(jì)的計(jì)算機(jī)算法進(jìn)行工作，計(jì)算機(jī)算法作為計(jì)算機(jī)程序的先導(dǎo)和運(yùn)行基礎(chǔ)，與數(shù)據(jù)結(jié)構(gòu)共同構(gòu)成計(jì)算機(jī)程序。在解決具體實(shí)際的問題時，計(jì)算機(jī)算法具有運(yùn)算序列，進(jìn)行具體運(yùn)算描述。計(jì)算機(jī)算法分為兩大類：（一）數(shù)值運(yùn)算算法；（二）非數(shù)值運(yùn)算算法。對于具體實(shí)際問題，選擇精確高效的算法和設(shè)計(jì)準(zhǔn)確高效的算法能更加快速高效的解決問題。

1 計(jì)算機(jī)算法的特點(diǎn)和分類

1.1 計(jì)算機(jī)算法的特點(diǎn)。

1.1.1 有窮性。算法的步驟應(yīng)該是有限的，超過合理的限度通常認(rèn)為是無效算法。

1.1.2 確定性。算法設(shè)計(jì)中的每一步驟都是確定的，必須被解釋成唯一的算法含義。

1.1.3 有零個或多個輸入。執(zhí)行算法時的執(zhí)行信息。

1.1.4 有一個或多個輸出。算法的執(zhí)行是為了得到問題的結(jié)果，得不出結(jié)果的算法是沒有意義的。

1.1.5 有效性。算法設(shè)計(jì)中的每一個步驟都必須有效執(zhí)行，得到確定的結(jié)果。

1.2 計(jì)算機(jī)算法的分類

計(jì)算機(jī)算法分為兩大類：1.數(shù)值運(yùn)算算法。包括迭代法、遞推法和遞歸法等；2.非數(shù)值運(yùn)算算法。包括窮舉法、分治法、貪心法和回溯法等。

2 計(jì)算機(jī)算法的設(shè)計(jì)和分析

在設(shè)計(jì)計(jì)算機(jī)算法時，要結(jié)合實(shí)際問題，對已存在的計(jì)算機(jī)算法作出合理的分析和判斷，必要時重新設(shè)計(jì)更加準(zhǔn)確高效的算法以達(dá)到計(jì)算機(jī)在執(zhí)行時采用最優(yōu)算法的標(biāo)準(zhǔn)，減少解決問題的時間，提升解答問題時的準(zhǔn)確性。在進(jìn)行計(jì)算機(jī)算法的設(shè)計(jì)和分析時主要從以下幾個方面進(jìn)行考慮：

2.1 計(jì)算機(jī)算法復(fù)雜性問題

計(jì)算復(fù)雜性是計(jì)算理論中的一個特點(diǎn)，研究計(jì)算問題時所需的資源，比如時間和空間，以及如何盡可能的節(jié)省這些資源。最常見的是時間(要通過多少步才能解決問題)和空間(在解決問題時需要多少內(nèi)存)。時間復(fù)雜度是指在計(jì)算機(jī)科學(xué)與工程領(lǐng)域內(nèi)完成一個算法所需的時間，是衡量一個算法優(yōu)劣的重要參數(shù)。時間復(fù)雜度越小，說明該算法效率越高，則該算法越有價值。空間復(fù)雜度是指計(jì)算機(jī)科學(xué)領(lǐng)域完成一個算法所需要占用的存儲空間，一般是輸入?yún)?shù)的函數(shù)。它是算法優(yōu)劣的重要度量指標(biāo)，一般來說，空間復(fù)雜度越小，算法越好。

2.2 計(jì)算機(jī)算法穩(wěn)定可靠性問題

計(jì)算機(jī)算法的運(yùn)行穩(wěn)定性可以作為衡量算法的一個評價標(biāo)準(zhǔn)。具體反映在面對給定的錯誤指令時，計(jì)算機(jī)算法自身能具有較強(qiáng)的判斷力和決策能力。判斷力高的計(jì)算機(jī)算法可以降低執(zhí)行時反復(fù)核實(shí)運(yùn)算流程，高決策能力的計(jì)算機(jī)算法可以有效控制運(yùn)算進(jìn)行時不受錯誤指令反復(fù)累積迭代的影響，從而避免反復(fù)運(yùn)算的現(xiàn)象。

2.3 計(jì)算機(jī)算法最優(yōu)化問題

在處理遇到的問題時，計(jì)算機(jī)算法自身可能得不到最優(yōu)解集。計(jì)算機(jī)會受到約束條件的干擾，從算法自己中選擇比較相似的或者靠近最優(yōu)解集的運(yùn)算路徑，在這種錯誤的最優(yōu)化路徑下，輸出計(jì)算結(jié)果。在有些算法中，算法在執(zhí)行時設(shè)置了不存在最優(yōu)解集的條件限制，計(jì)算機(jī)會輸出模糊的解集。如果不限定有限閾值，在判定最優(yōu)值時，會輸出算法的平均性分析結(jié)果。或者是最差的運(yùn)算指標(biāo)標(biāo)準(zhǔn)。類似的算法比較適用于簡化的情況，不太能滿足復(fù)雜程度高的運(yùn)算問題。在反復(fù)運(yùn)算找最優(yōu)解集的過程中，自身的時間和空間消耗降低了運(yùn)算效率。

2.4 計(jì)算機(jī)算法的其它相關(guān)問題

在計(jì)算機(jī)的算法設(shè)計(jì)和分析中，還要多方面考慮計(jì)算機(jī)算法分析的其他存在的相關(guān)問題，如計(jì)算機(jī)算法的自適應(yīng)問題、計(jì)算機(jī)算法的精巧性、實(shí)現(xiàn)約束能力、計(jì)算機(jī)算法的簡明性等。

3 計(jì)算機(jī)優(yōu)化算法的評價標(biāo)準(zhǔn)

通過對有n項(xiàng)的線性表的順序搜索算法分析和二分法分析，通常情況下，無序表的查找只能靠順序檢索查找計(jì)算機(jī)算法，平均查找長度為（n+1）/2,而二分法的查找長度更短。在具體的應(yīng)用中，一般先把無序線性表的計(jì)算機(jī)算法轉(zhuǎn)化成有序線性表，能大大節(jié)省查找的時間。在此過程中，要合理分析計(jì)算機(jī)算法的最壞情況及平均性狀。這一過程看似簡單，工作量卻很大。對于常用的算法，可以參考算法資料來獲取相關(guān)信息。對于常用的計(jì)算機(jī)算法，用戶可以引用已存在的比較復(fù)雜的估算公式，對算法進(jìn)行評估，看是否滿足應(yīng)用時的需求。對于特別復(fù)雜的計(jì)算機(jī)算法，可以作簡單的數(shù)量級估計(jì)，定量抽象描述計(jì)算機(jī)算法的復(fù)雜性。

4 結(jié)束語

在遇到具體問題時，要充分掌握計(jì)算機(jī)的工作原理和算法執(zhí)行方式，以便更好的分析和設(shè)計(jì)計(jì)算機(jī)算法，對于實(shí)際問題的特征，選擇最優(yōu)的算法設(shè)計(jì)方案，從而更加精確和高效的提升計(jì)算機(jī)算法的執(zhí)行效率，更加快速高效的解決問題。