（一）算法
1．算法的基本概念
算法是指解題方案的準(zhǔn)確而完整的描述。即是一組嚴(yán)謹(jǐn)?shù)囟x運算順序的規(guī)則，并且每一個規(guī)則都是有效的，且是明確的，沒有二義性，同時該規(guī)則將在有限次運算后可終止。
1）算法的基本特征
（1）可行性
由于算法的設(shè)計是為了在某一個特定的計算工具上解決某一個實際的問題而設(shè)計的，因此，它總是受到計算工具的限制，使執(zhí)行產(chǎn)生偏差。
如：計算機的數(shù)值有效位是有限的，當(dāng)大數(shù)和小數(shù)進行運算時，往往會因為有效位數(shù)的影響而使小數(shù)丟失，因此，在算法設(shè)計時，應(yīng)該考慮到這一點。
（2）確定性
算法的設(shè)計必須是每一個步驟都有明確的定義，不允許有模糊的解釋，也不能有多義性。
例如，一個實際的問題，小寶和萍萍共有12個蘋果，小寶比萍萍多4個，請問小寶和萍萍各有幾個蘋果？這個問題，我們可以立一個方程組x+y=12和x-y=4來求解，要求x和y的值，公式是正確的，但如何讓計算能夠進行計算，我們的算法不能把公式直接輸進去，而應(yīng)該設(shè)計出解題的步驟和過程。
即設(shè)計的算法是計算工具所能夠正常解決問題的過程。
（3）有窮性
算法的有窮性，即在一定的時間是能夠完成的，即算法應(yīng)該在計算有限個步驟后能夠正常結(jié)束。
例如，在數(shù)學(xué)中的無窮級數(shù)，在計算機中只能求有限項，即計算的過程是有窮的。
（4）擁有足夠的情報
算法的執(zhí)行與輸入的數(shù)據(jù)和提供的初始條件相關(guān)，不同的輸入或初始條件會有不同的輸出結(jié)果，提供準(zhǔn)確的初始條件和數(shù)據(jù)，才能使算法正確執(zhí)行。
2）算法的基本要素
一是數(shù)據(jù)對象的運算和操作，二是算法的控制結(jié)構(gòu)。
（1）算法中對數(shù)據(jù)的運算和操作
算法實際上是按解題要求從環(huán)境能進行的所有操作中選擇合適的操作所組成的一組指令序列。即算法是計算機所能夠處理的操作所組成的指令序列。
（2）算法的控制結(jié)構(gòu)
算法的功能不僅取決于所選用的操作，而且還與各操作之間的順序有關(guān)。
在算法中，操作的執(zhí)行順序又稱算法的控制結(jié)構(gòu)，一般的算法控制結(jié)構(gòu)有三種：順序結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)。
在算法描述是，有相關(guān)的工具對這三種結(jié)構(gòu)進行描述，常用的描述工具有：流程圖、N-S結(jié)構(gòu)圖和算法描述語言等。
3）算法設(shè)計的基本方法
為用計算機解決實際問題而設(shè)計的算法，即是計算機算法。
通常的算法設(shè)計有如下幾種：
（1）列舉法
列舉法的基本思想是，根據(jù)提出的問題，列舉出所有可能的情況，并用問題中給定的條件檢驗?zāi)男┦菨M足條件的，哪些是不滿足條件的。列舉法通常用于解決“是否存在”或“有哪些可能”等問題。
例如，我國古代的趣味數(shù)學(xué)題：“百錢買百雞”、“雞兔同籠”等，均可采用列舉法進行解決。
使用列舉法時，要對問題進行詳細的分析，將與問題有關(guān)的知識條理化、完備化、系統(tǒng)化，從中找出規(guī)律。
（2）歸納法
歸納法的基本思想是，通過列舉少量的特殊情況，經(jīng)過分析，最后找出一般的關(guān)系。歸納是一種抽象，即從特殊現(xiàn)象中找出一般規(guī)律。但由于在歸納法中不可能對所有的情況進行列舉，因此，該方法得到的結(jié)論只是一種猜測，還需要進行證明。
（3）遞推
遞推，即是從已知的初始條件出發(fā)，逐次推出所要求的各個中間環(huán)節(jié)和最后結(jié)果。其中初始條件或問題本身已經(jīng)給定，或是通過對問題的分析與化簡而確定。
遞推的本質(zhì)也是一種歸納，遞推關(guān)系式通常是歸納的結(jié)果。
例如，裴波那契數(shù)列，是采用遞推的方法解決問題的。
（4）遞歸
在解決一些復(fù)雜問題時，為了降低問題的復(fù)雜程序，通常是將問題逐層分解，最后歸結(jié)為一些最簡單的問題。這種將問題逐層分解的過程，并沒有對問題進行求解，而只是當(dāng)解決了最后的問題那些最簡單的問題后，再沿著原來分解的逆過程逐步進行綜合，這就是遞歸的方法。
遞歸分為直接遞歸和間接遞歸兩種方法。如果一個算法直接調(diào)用自己，稱為直接遞歸調(diào)用；如果一個算法A調(diào)用另一個算法B，而算法B又調(diào)用算法A，則此種遞歸稱為間接遞歸調(diào)用。
（5）減半遞推技術(shù)
減半遞推即將問題的規(guī)模減半，然后，重復(fù)相同的遞推操作。
例如，一元二次方程的求解。
（6）回溯法
有些實際的問題很難歸納出一組簡單的遞推公式或直觀的求解步驟，也不能使用無限的列舉。對于這類問題，只能采用試探的方法，通過對問題的分析，找出解決問題的線索，然后沿著這個線索進行試探，如果試探成功，就得到問題的解，如果不成功，再逐步回退，換別的路線進行試探。這種方法，即稱為回溯法。
如人工智能中的機器人下棋。
2．算法復(fù)雜度
算法的復(fù)雜度包括時間復(fù)雜度和空間復(fù)雜度。
1）時間復(fù)雜度
即實現(xiàn)該算法需要的計算工作量。算法的工作量用算法所執(zhí)行的基本運算次數(shù)來計算。
同一個問題規(guī)模下，如果算法執(zhí)行所需要的基本次數(shù)取決于某一特定輸入時，可以用以下兩種方法來分析算法的工作量：
算法工作量=f(n)
（1）平均性態(tài)
用各種特定輸入下的基本運算次數(shù)的加權(quán)平均值來度量算法的工作量。
設(shè)x是某個可能輸入中的某個特定輸入，p(x)是x出現(xiàn)的概率，t(x)是算法在輸入為x時所執(zhí)行的基本運算次數(shù)，則算法的平均性態(tài)定義為：
Dn表示當(dāng)規(guī)模為n時，算法執(zhí)行時所有可能輸入的集合。
（2）最壞情況復(fù)雜度
指在規(guī)模為n時，算法所執(zhí)行的基本運算的次數(shù)。它定義為：
例如，在具有n個元素的數(shù)列中搜索一個數(shù)x。
平均性態(tài)：
即該數(shù)在數(shù)列中任何位置出現(xiàn)的數(shù)列是相同的，也有可能不存在，存在的概率為q。
如果有一半的機會存在，則概率q為1/2，平均性態(tài)：
如果查找的元素一定在數(shù)列中，則每個數(shù)存在的概率即為1，則平均性態(tài)為：
最壞情況分析：即要查找的元素X在數(shù)列的最后或不在數(shù)列中，顯然，它的最壞情況復(fù)雜度為：
2）算法的空間復(fù)雜度
指要執(zhí)行該算法所需要的內(nèi)存空間。算法所占用的內(nèi)存空間包括算法程序所占的空間、輸入的初始數(shù)據(jù)所占的存儲空間以及算法執(zhí)行過程中所需要的額外空間，如執(zhí)行過程中工作單元以及某種數(shù)據(jù)結(jié)構(gòu)所需要的附加存儲空間等。