1.1 演算法
考點1 演算法的基本概念
計算機解題的過程實際上是在實施某種演算法，這種演算法稱為計算機演算法。
演算法(algorithm)是一組嚴謹地定義運算順序的規則，並且每乙個規則都是有效的，同時是明確的；此順序將在有限的次數後終止。演算法是對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示乙個或多個操作。
1演算法的基本特徵
(1)可行性(effectiveness)：針對實際問題而設計的演算法，執行後能夠得到滿意的結果。
(2)確定性(definiteness)：演算法中的每乙個步驟都必須有明確的定義，不允許有模稜兩可的解釋和多義性。
(3)有窮性(finiteness)：演算法必需在有限時間內做完，即演算法必需能在執行有限個步驟之後終止。
(4)擁有足夠的情報：要使演算法有效必需為演算法提供足夠的情報當演算法擁有足夠的情報時，此演算法才最有效的；而當提供的情報不夠時，演算法可能無效。
2演算法的基本要素
(1)演算法中對資料的運算和操作：每個演算法實際上是按解題要求從環境能進行的所有操作中選擇合適的操作所組成的一組指令序列。
計算機可以執行的基本操作是以指令的形式描述的。乙個計算機系統能執行的所有指令的集合，稱為該計算機系統的指令系統。電腦程式就是按解題要求從計算機指令系統中選擇合適的指令所組成的指令序列在一般的計算機系統中，基本的運算和操作有以下4類：
①算術運算：主要包括加、減、乘、除等運算；
②邏輯運算：主要包括「與」、「或」、「非」等運算；
③關係運算：主要包括「大於」、「小於」、「等於」、「不等於」等運算；
④資料傳輸：主要包括賦值、輸入、輸出等操作。
(2)演算法的控制結構：乙個演算法的功能不僅僅取決於所選用的操作，而且還與各操作之間的執行順序有關。演算法中各操作之間的執行順序稱為演算法的控制結構。
演算法的控制結構給出了演算法的基本框架，它不僅決定了演算法中各操作的執行順序，而且也直接反映了演算法的設計是否符合結構化原則。描述演算法的工具通常有傳統流程圖、n-s結構化流程圖、演算法描述語言等。乙個演算法一般都可以用順序、選擇、迴圈3種基本控制結構組合而成。
(3)演算法設計的基本方法
計算機演算法不同於人工處理的方法，下面是工程上常用的幾種演算法設計，在實際應用時，各種方法之間往往存在著一定的聯絡。
(1)列舉法
列舉法是計算機演算法中的乙個基礎演算法。列舉法的基本思想是，根據提出的問題，列舉所有可能的情況，並用問題中給定的條件檢驗哪些是需要的，哪些是不需要的。
列舉法的特點是演算法比較簡單。但當列舉的可能情況較多時，執行列舉演算法的工作量將會很大。因此，在用列舉法設計演算法時，使方案優化，儘量減少運算工作量，是應該重點注意的。
(2)歸納法
歸納法的基本思想是，通過列舉少量的特殊情況，經過分析，最後找出一般的關係。從本質上講，歸納就是通過觀察一些簡單而特殊的情況，最後總結出一般性的結論。
(3)遞推
遞推是指從已知的初始條件出發，逐次推出所要求的各中間結果和最後結果。其中初始條件或是問題本身已經給定，或是通過對問題的分析與化簡而確定。遞推本質上也屬於歸納法，工程上許多遞推關係式實際上是通過對實際問題的分析與歸納而得到的，因此，遞推關係式往往是歸納的結果。
對於數值型的遞推演算法必須要注意數值計算的穩定性問題。
(4)遞迴
人們在解決一些複雜問題時，為了降低問題的複雜程度(如問題的規模等)，一般總是將問題逐層分解，最後歸結為一些最簡單的問題。這種將問題逐層分解的過程，實際上並沒有對問題進行求解，而只是當解決了最後那些最簡單的問題後，再沿著原來分解的逆過程逐步進行綜合，這就是遞迴的基本思想。
遞迴分為直接遞迴與間接遞迴兩種。
(5)減半遞推技術
實際問題的複雜程度往往與問題的規模有著密切的聯絡。因此，利用分治法解決這類實際問題是有效的。工程上常用的分治法是減半遞推技術。
所謂「減半」，是指將問題的規模減半，而問題的性質不變；所謂「遞推」，是指重複「減半」的過程。
(6)回溯法
在工程上，有些實際問題很難歸納出一組簡單的遞推公式或直觀的求解步驟，並且也不能進行無限的列舉。對於這類問題，一種有效的方法是「試」。通過對問題的分析，找出乙個解決問題的線索，然後沿著這個線索逐步試探，若試探成功，就得到問題的解，若試探失敗，就逐步回退，換別的路線再逐步試探。
4演算法設計的要求
通常乙個好的演算法應達到如下目標：
(l)正確性(correctness)
正確性大體可以分為以下4個層次：
①程式不含語法錯誤；
②程式對於幾組輸入資料能夠得出滿足規格說明要求的結果；
③程式對於精心選擇的典型、苛刻而帶有刁難性的幾組輸入資料能夠得出滿足規格說明要求的結果；
④程式對於一切合法的輸入資料都能產生滿足規格說明要求的結果。
(2)可讀性(readability)
演算法主要是為了方便入的閱讀與交流，其次才是其執行。可讀性好有助於使用者對演算法的理解；晦澀難懂的程式易於隱藏較多錯誤，難以除錯和修改。
(3)健壯性(robustness)
當輸入資料非法時，演算法也能適當地做出反應或進行處理，而不會產生莫名其妙的輸出結果。
(4)效率與低儲存量需求
效率指的是程式執行時，對於同乙個問題如果有多個演算法可以解決，執行時間短的演算法效率高；儲存量需求指演算法執行過程中所需要的最大儲存空間
考點2 演算法的複雜度
1演算法的時間複雜度
演算法的時間複雜度，是指執行演算法所需要的計算工作量。同乙個演算法用不同的語言實現，或者用不同的編譯程式進行編譯，或者在不同的計算機上執行，效率均不同。這表明使用絕對的時間單位衡量演算法的效率是不合適的。
撇開這些與計算機硬體、軟體有關的因素，可以認為乙個特定演算法「執行工作量」的大小，只依賴於問題的規模(通常用整數n表示)，它是問題的規模函式。即
演算法的工作量=f(n)
例如，在n×n矩陣相乘的演算法中，整個演算法的執行時間與該基本操作(乘法)重複執行的次數n3成正比，也就是時間複雜度為n3，即
f(n)=o(n3)
在有的情況下，演算法中的基本操作重複執行的次數還隨問題的輸入資料集不同而不同。例如在起泡排序的演算法中，當要排序的陣列a初始序列為自小至大有序時，基本操作的執行次數為氏當初始序列為自大至小有序時，基本操作的執行次數為n(n- 1)/2。對這類演算法的分析，可以採用以下兩種方法來分析。
(1)平均性態(**erage beh**ior)
所謂平均性態是指各種特定輸入下的基本運算次數的加權平均值來度量演算法的工作量。
設x是所有可能輸入中的某個特定輸入，p(x)是x出現的概率(即輸入為x的概率)，t(x)是演算法在輸入為x時所執行的基本運算次數，則演算法的平均性態定義為
其中dn表示當規模為n時，演算法執行的所有可能輸入的集合。
(2)最壞情況複雜性(worst-case complexity)
所謂最壞情況分析，是指在規模為n時，演算法所執行的基本運算的最大次數。
2演算法的空間複雜度
演算法的空間複雜度是指執行這個演算法所需要的記憶體空間。
乙個演算法所占用的儲存空間包括演算法程式所佔的空間、輸入的初始資料所佔的儲存空間以及演算法執行中所需要的額外空間。其中額外空間包括演算法程式執行過程中的工作單元以及某種資料結構所需要的附加儲存空間。如果額外空間量相對於問題規模來說是常數，則稱該演算法是原地(in place)工作的。
在許多實際問題中，為了減少演算法所佔的儲存空間，通常採用壓縮儲存技術，以便儘量減少不必要的額外空間。
考點3 資料結構的定義
資料結構(data structure)是指相互之間存在一種或多種特定關係的資料元素的集合，即資料的組織形式。
資料結構作為計算機的一門學科，主要研究和討論以下三個方面：
(l)資料集合中個資料元素之間所固有的邏輯關係，即資料的邏輯結構；
(2)在對資料元素進行處理時，各資料元素在計算機中的儲存關係，即資料的儲存結構；
(3)對各種資料結構進行的運算。
討論以上問題的日的是為了提高資料處理的效率，所謂提高資料處理的效率有兩個方面：
(l)提高資料處理的速度；
(2)盡量節省在資料處理過程中所占用的計算機儲存空間。
資料(data)：是對客觀事物的符號表示，在電腦科學中是指所有能輸入到計算機中並被電腦程式處理的符號的總稱。
資料元素(data element)：是資料的基本單位，在電腦程式中通常作為乙個整體進行考慮和處理。
資料物件(data object)：是性質相同的資料元素的集合，是資料的乙個子集。
在一般情況下，在具有相同特徵的資料元素集合中，各個資料元素之間存在有某種關係(即連續)，這種關係反映了該集合中的資料元素所固有的一種結構。在資料處理領域中，通常把資料元素之間這種固有的關係簡單地用前後件關係(或直接前驅與直接後繼關係)來描述。
前後件關係是資料元素之間的乙個基本關係，但前後件關係所表示的實際意義隨具體物件的不同而不同。一般來說，資料元素之間的任何關係都可以用前後件關係來描述。
1資料的邏輯結構
資料結構是指反映資料元素之間的關係的資料元素集合的表示。更通俗地說，資料結構是指帶有結構的資料元素的集合。所謂結構實際上就是指資料元素之間的前後件關係。
乙個資料結構應包含以下兩方面資訊：
(1)表示資料元素的資訊；
計算機二級考試公共基礎知識
第1章資料結構與演算法 1.1 演算法的複雜度 1.演算法的基本概念 利用計算機演算法為計算機解題的過程實際上是在實施某種演算法。1 演算法的基本特徵 演算法一般具有4個基本特徵 可行性 確定性 有窮性 擁有足夠的情報。2 演算法的基本運算和操作 演算法的基本運算和操作包括 算術運算 邏輯運算 關係...
計算機二級C公共基礎知識總結
第一章資料結構與演算法 1.1 演算法 演算法 是一組有窮指令集，是解題方 而完整的描述。通俗地說，演算法就是計算機解題的過程。演算法不等於程式，也不等於計算方法，程式的編制不可能優於演算法的設計。演算法是一組嚴謹地定義運算順序的規則，每乙個規則都是有效的，且是明確的，此順序將在有限的次數下終止。所...
計算機二級基礎知識
第一章資料結構與演算法 一 學習目標與要求 1 了解演算法的基本概念和一些常用的演算法，學會計算演算法的時間複雜度 2 掌握資料結構的基本概念，並了解資料的邏輯結構和儲存結構，學會利用圖形的方式表示資料結構 3 了解線性表的基本概念，並掌握線性表的順序儲存結構以及順序儲存的線性表的基本運算 4 了解...