數據結構（c++）鄧俊暉

緒論

計算機與算法

算法

所謂算法，是指基于特定的計算模型，旨在解決某一信息處理問題而設計的一個指令序列。

算法要素：

• 輸入與輸出

待計算問題的任一實例，都需要以某種方式交給對應的算法，對所求解問題特定實例的這種描述統稱為輸入（input）；經過計算和處理之后得到的信息，即針對輸入問題實例的答案，稱作輸出（output）。

• 基本操作、確定性與可行性

所謂確定性和可行性是指，算法應可描述為若干語義明確的基本操作組成的指令序列，且每一基本操作在對應的計算模型中均可兌現。一個算法滿足確定性和可行性，當且僅當它可以通過程序設計語言精確地描述。

• 有窮性與正確性

任意算法都應在執行有限次基本操作之后終止并給出輸出，此即所謂算法的有窮性（finiteness）。進一步地，算法不僅應該遲早會終止，而且所給的輸出還應該能夠符合由問題本身在事先確定的條件，此即所謂算法的正確性（correctness）。

證明算法的有窮性和正確性的一個重要技巧，就是從適當的角度審視整個計算過程，并找出其所具有的某種不變性和單調性。其中的單調性通常是指，問題的有效規模會隨著算法的推進不斷遞減。不變性則不僅在算法初始狀態下自然滿足，而且應與最終的正確性相呼應-當問題的有效規模縮減到0時，不變性隨即等價于正確性。

• 退化與魯棒性

同一問題往往不限于一種算法，而統一算法也常常會有多種實現方式，因此除了以上必須具備的基本屬性，在應用環境中還需從實用的角度對不同算法及其不同版本做更為細致考量和取舍。這些細致的要求盡管應納入軟件工程的范疇，但也不失為成熟算法的重要標志。

比如其中之一就是，除一般性情況外，實用的算法還應能夠處理各種極端的輸入實例。以排序問題為例，極端情況下待排序序列的長度可能不是整數（參數n=0甚至n<0），或者反過來長度達到或者超過系統支持的最大值(n=INT_MAX),或者A[]中的元素不見得互異甚至全體相等，以上種種都屬于所謂的退化（degeneracy）情況。算法所謂的魯棒性（robustness），就是要求能夠盡可能充分地應對此類情況。

• 重用性

從實用角度評判不同算法及其不同實現方式時，可采用的另一標準是：算法的總體框架能否便捷地推廣至其它場合。以冒泡排序為例，冒泡算法的正確性與所處理序列中元素的類型關系不大，無論是對于float、char或者其他類型，只要元素之間可以比較大小，算法的整體框架就依然可以沿用。算法模式可推廣并適用于不同類型基本元素的這種特性，即是重用性的一種典型形式。

算法效率

• 可計算性（computability）
• 難解性（intractability）
• 計算效率

首先需要確立一種尺度，用以從時間和空間等方面度量算法的計算成本，進而依此尺度對不同算法進行比較和評判。當然，更重要的是研究和歸納算法設計與實現過程中的一般性規律與技巧，以編寫出效率更高、能夠處理更大規模數據的程序。

• 數據結構

數據結構這一學科以“數據”這一信息的表現形式為研究對象，旨在建立支持高效算法的數據信息處理策略、技巧和方法。要做到根據實際應用需求自如地設計、實現和選用適當的數據結構，必須對算法設計的技巧以及相應數據結構的特性了然于心。

復雜度度量

時間復雜度

為針對運行時間建立起一種可行、可信的評估標準，我們不得不首先考慮其中最為關鍵的因素-問題實例的規模。一般地，問題規模越接近，相應的計算成本也越接近；而隨著問題規模的擴大，計算成本通常也呈上升趨勢。

隨著輸入規模的擴大，算法執行時間將如何增長？執行時間的這一變化趨勢可表示為輸入規模的一個函數，稱作該算法的時間復雜度（time complexity）。具體地，特定算法處理規模為n的問題所需要的時間記作T(n)。

根據規模并不能唯一確定具體的輸入，規模相同的輸入通常都有多個，而算法對其進行處理所需要時間也不盡相同。嚴格來說，以上定義的T(n)并不明確，為此需要再做一次簡化，即從保守估計的角度出發，在規模為n的所有輸入中選擇執行時間最長者作為T(n)，并以T(n)度量該算法的時間復雜度。

漸進復雜度

對于同一問題的兩個算法A和B,通過比較其時間復雜度T_A(n)和T_B(n)，即可評價二者對于同一輸入規模n的計算效率高低。然而，籍此還不足以就其性能優劣做出總體性的評判，例如對于某些問題，一些算法更適合用于小規模輸入，而另一些則相反。

幸運的是，在評價算法運行效率時，我們往往可以忽略其處理小規模問題時的能力差異，轉而關注其在處理更大規模問題時的表現。其中的原因不難理解，小規模問題所需的處理時間本來就相對更少，故此時不同算法的實際效率差異并不明顯；而在處理更大規模的問題時，效率的些許差異都將對實際執行效果產生巨大的影響。這種著眼長遠、更為注重實踐復雜度的總體變化趨勢和增長速度的策略和方法，即所謂的漸進分析（asymptotic analysis）。

那么，針對足夠大的輸入規模n，算法執行時間T(n)的漸進增長速度，應如何度量和評價呢？

• 大δ記號

同樣地出于保守的估計，我們首先關注T(n)的漸進上界。為此可引入所謂“大δ記號”（big-δ notation）。具體地，若存在正的常數c和函數f(n)，使得對任何n>>2都有T(n)≤c·f(n)則可認為在n足夠大之后，f(n)給出了T(n)增長速度的一個漸進上界。此時，記之為：T(n) = δ(f(n))由這一定義，可導出大δ記號的一下性質：

（1）對于任一常數c>0，有δ(f(n))=δ(c·f(n))

（2）對于任意常數a>b>0，有δ(n^a + n^b)=δ(n^a)

前一性質意味著，在大δ記號的意義下，函數各項正的常系數可以忽略并等同于1.后一性質則意味著，多項式中的低次項均可忽略，只需要保留最高此項。可以看出，大δ記號的這些性質的確體現了對函數總體漸進增長趨勢的關注和刻畫。

• 環境差異

在實際環境中直接測得的執行時間T(n)，雖不失為衡量算法性能的一個指標，但作為評判不同算法性能優劣的標準，其可信度值得推敲。事實上，即便是同一算法、同一輸入，在不同的硬件平臺上、不同的操作系統中甚至不同的時間，所需要的計算時間都不盡相同。因此，有必要按照超脫于具體硬件平臺和軟件環境的某一客觀標準，來度量算法的時間復雜度，并進而評價不同算法的效率差異。

• 基本操作

一種自然且可行的解決辦法是，將時間復雜度理解為算法中各條指令的執行時間之和。在圖靈機(Turing Machine,TM)和隨機存儲機(Random Access Machine,RAM)等計算模型中，指令語句均分解為若干次基本操作，比如算術運算、比較、分支、子程序調用與返回等；而在大多數實際的計算環境中，每一次這類基本操作都可在常數時間內完成。

如此，不妨將T(n)定義為算法所執行基本操作的總次數。也就是說，T(n)決定于組成算法的所有語句各自的執行次數，以及其中所含基本操作的數目。

• 最壞、最好和平均情況

以大δ記號形式表示的時間復雜度，實質上是對算法執行時間的一種保守估計-對于規模為n的 任意輸入，算法的運行時間都不會超過δ(f(n))。比如“冒泡排序算法時間復雜度T(n)=δ(n²)”意味著，該算法處理任何序列所需要的時間絕不會超過δ(n²)。的確需要這么長計算時間的輸入實例，稱作最壞實例或最壞情況（worst case）。

需要強調的是，這種保守估計并不排斥更好情況甚至最好情況（best case）的存在和出現。比如，對于某些輸入序列，冒泡排序算法的內循環的執行輪數可能少于n-1，甚至只需執行一輪。當然，有時也需要考察所謂的平均情況（average case），也就是按照某種約定的概率分布，將規模為n的所有輸入對應的計算時間加權平均。

比較而言，“最壞情況復雜度”是人們最為關注且使用最多的，在一些特殊的場合甚至成為唯一的指標。比如控制核電站運轉、管理神經外科手術室現場的系統而言，從最好或平均角度評判算法的響應速度都不具有任何意義，在最壞情況下的響應速度才是唯一的指標。

• 大Ω記號

為了對算法的復雜度最好情況做出設計，需要借助另一個記號。如果存在正的常數c和函數g(n)，使得對于任何n>>2都有T(n)≥c·g(n)就可以認為，在n足夠大之后，g(n)給出了T(n)的一個漸進下界。此時，我們記之為：T(n)=Ω(g(n))

這里的Ω稱作“大Ω記號”（big-omega notation）。與大δ記號恰好相反，大Ω記號是對算法執行效率的樂觀估計-對于規模為n的任意輸入，算法的運行時間都不低于Ω(g(n))。比如，即便在最好情況下，冒泡排序也至少需要T(n)=Ω(n)的計算時間。

• 大Θ記號

借助大δ記號、大Ω記號，可以對算法的時間復雜度作出定量的界定，亦即，從漸進的趨勢看，T(n)介于Ω(g(n))與δ(f(n))之間。若恰巧出現g(n)=f(n)的情況，則可以使用另一種記號來表示。

如果存在正的常數c₁<c₂和函數h(n)，使得對于任何n>>2都有

c₁·h(n)≤T(n)≤c₂·h(n)

就可以認為n在足夠大之后，h(n)給出了T(n)的一個確界。此時，我們記之為：T(n)=Θ(h(n))

這里的Θ稱作“大Θ記號”（big-theta notation），它是對算法復雜度的準確估計-對于規模為n的任何輸入，算法的運行時間T(n)都與Θ(h(n))同階。

以上就是這三種漸進復雜度記號之間的聯系與區別，可由上圖示意。

空間復雜度

除了執行時間的長短，算法所需存儲空間的多少也是衡量其性能的一個重要方面，此即所謂的空間復雜度（space complexity）。實際上，以上針對時間復雜度所引入的幾種漸進記號，也適用于對空間復雜度的度量，其原理及方法基本相同，不再贅述。

需要注意的是，為了更客觀地評價算法性能的優劣，除非特別申明，空間復雜度通常并不計入原始輸入本身所占用的空間-對于同一問題，這一指標對任何算法都是相同的。反之，其它（如轉儲、中轉、索引、映射、緩沖等）各個方面所消耗的空間，則都應計入。

另外，很多時候我們都是更多地甚至僅僅關注算法是時間復雜度，而不必對空間復雜度做專門的考查。這種簡便評測方式的依據，來自于一下事實：就漸進復雜的意義而言，在任一算法的任何一次運行過程中所消耗的存儲空間，都不會多于其間所執行基本操作的累計次數。

實際上根據定義，每次基本操作所涉及的存儲空間，都不會超過常數規模；縱然每次基本操作所占用或訪問的存儲空間都是新開辟的，整個算法所需要的空間總量，也不過與基本操作的次數同階。從這個意義上說，時間復雜度本身就是空間復雜度的一個天然的上界。

當然，對空間復雜度的分析也有其自身的意義，尤其在對空間效率非常在乎的應用場合中，或當問題的輸入規模極為龐大時，由時間復雜度所確立的平凡上界已經難以讓人滿意。這類情況下，人們將更為精細地考查不同算法的空間效率，并盡力在此方面不斷優化。

復雜度分析

常數δ(1)

• 問題與算法

考察如下常規元素的選取問題，該問題一種解法如算法1.3所示。

ordinaryElement(S[], n) //從n≥3個互異整數中，除最大、最小者以外，任取一個“常規元素” 任取的三個元素x,y,z ∈S;//這三個元素亦比互異 通過比較，對它們做排序;//設經排序后，依次重命名為：a<b<c 輸出b; 算法1.3 取非極端元素

該算法的正確性不言而喻，但它需要運行多少時間？與輸入的規模n有何聯系？

• 復雜度

既然S是有限集，故其中的最大、最小元素各有且僅有一個。因此，無論S的規模有多大，在任意三個元素中至少都有一個是非極端元素。不妨取前三個x=S[0]、y=S[1]、z=S[2]，這一步只需執行三次（從特定單元讀取元素的）基本操作，耗費δ(3)時間。接下來，為確定這三個元素的大小次序，最多需要做三次比較，也需要δ(3)時間。最后，輸出居中的非極端元素只需要δ(1)時間。因此綜合起來，算法1.3的運行時間為：
$$T(n)=\delta (3)+\delta (3)+\delta (1)=\delta (7)=\delta (1)$$
運行時間可表示和度量為T(n)=δ(1)的這一類算法，統稱作“常數時間復雜度算法”（constant-time algorithm）。此類算法已經是最為理想的，因為不可能奢望“不勞而獲”。

一般地，僅含一次或常數次基本操作的算法均屬于此類。此類算法通常不含循環、分支、子程序調用等，但也不能僅憑語法結構的表面形式一概而論。

除了輸入數組等參數之外，該算法僅需常數規模的輔助空間。此類僅需δ(1)輔助空間的算法，亦稱作就地算法（in-place algorithm）。

對數δ(logn)

• 問題與算法

考察如下問題：對于任意非負整數，統計其二進制展開中數位1的總數。

該問題的一個算法可實現如代碼1.2所示。該算法使用一個計數器ones記錄數位1的數目，其初始值為0.隨后進入一個循環：通過二進制位的與（and）運算，檢查n的二季之展開的最低位，若該位為1則累計至ones。由于每次循環都將n的二進制展開右移一位，故整體效果等同于逐個校驗所有位數是否為1，該算法的正確性也不難由此得證。

表1.1 countOnes(441)的執行過程 十進制二進制數位1計數

441	110111001	0
220	11011100	1
110	1101110	1
55	110111	1
27	11011	2
13	1101	3
6	110	4
3	11	4
1	1	5
0	0	6

以n=441₍₁₀₎=11011001₍₂₎為例，采用以上算法，變量n與計數器Ones在計算過程中的演變過程如表1.1所示。

int countOnes(unsigned int n){ //統計整數n的二進制展開中數位1的總數：0(logn)int ones = 0; //計數器復位while(0 <n){ //在縮減至0之前，若為1則計數ones += (1 & n); //檢查最低位，若為1則計數n >>= 1; //右移一位}return ones; //返回計數 } //等效與glibc的內置函數int _builtin_popcount(unsigned int n) 代碼1.2 整數二進制展開中數位1總數的統計

• 復雜度

根據右移運算的性質，每右移一位，n都至少縮減一半。就是說，至多經過1+「log₂n」次循環，n必然縮減至0，從而算法終止。實際上從另外一個角度看，1+「log₂n」恰為n二進制展開的總位數，每次循環都將其右移一位，總的循環次數自然也應該是1+「log₂n」。后一解釋，也可以從表1.1中n的二進制展開一列清晰地看出。

無論是該循環體之前、之內還是之后，均只涉及常數次（邏輯判斷、位與運算、加法、右移等）基本操作。因此，countOnes()算法的執行時間主要由循環的次數決定，也就是：

δ(1+「log₂n」) = δ(「log₂n」)=δ(log₂n)

由大δ記號定義，在用函數log_rn界定漸進復雜度時，常數底r的具體取值無所謂，故通常不予專門標出而籠統地記作logn。例如，盡管此時底數為常數2，卻可以直接記作δ(logn)。此類算法稱作具有“對數時間復雜度”（logarithmic-time algorithm）。

• 對數多項式復雜度

更一般地，凡運行時間可以表示和度量為T(n)=δ(log^cn)形式的這一類算法（其中常數c>0），均統稱作“對數多項式時間復雜度的算法”(polylogarithmic-time algorithm)。上述δ(logn)即c=1的特例。此類算法的效率雖不如常數復雜度算法理想，但從多項式的角度看仍能無限接近于后者，故也是極為高效的一類算法。

線性δ(n)

• 問題與算法

考察如下問題：計算給定n個整數的總和。該問題可由代碼1.3中的算法sumI()解決。

int sumI(int A[], int n){ //數組求和算法（迭代版）int sum = 0; //初始化累計器，O(1)for(int i = 0; i < n ; i++){ //對全部供O(n)個元素，逐一sum += A[i]; //累計，O(1)}return sum; //返回累計值，O(1) } //O(1)+O(n)*O(1)+O(1) = O(n+2) = O(n) 代碼1.3 數組元素求和算法sumI()

• 復雜度

sumI()算法的正確性一目了然，它需要運行多少時間呢？

首先，對s的初始化需要δ(1)時間。算法的主體部分是一個循環，每一輪循環中只需要進行一次累加，這屬于基本操作，可在δ(1)時間內完成。每經過一輪循環，都將一個元素累加至s，故總共需要做n輪循環，于是該算法的運行時間應為：
$$\delta (1)+\delta (1)?n=\delta (n+1)=\delta (n)$$
凡運行時間可以表示和度量為T(n) = δ(n)形式的這一類算法，均統稱為“線性時間復雜度算法”(linear-time algorithm)。比如，算法1.2只需要略加修改，即可解決“n等分給定線段”問題，這個通用版本相對于輸入n就是一個線性時間復雜度的算法。

也就是說，對于輸入的每一個單元，此類算法平均消耗常數時間。就大多數問題而言，在對輸入的每一單元至少訪問一次之前，不可能得出解答。以數組求和為例，在尚未得知每一元素的具體數值之前，絕不可能確定其總和。故就此意義而言，此類算法的效率亦足以令人滿意。

多項式δ(pllynomial(m))

若運行時間可以表示和度量為T(n)=δ(f(n))的形式，而且f(x)為多項式，則對應的算法稱作“多項式時間復雜度算法”(polynomial-time algorithm)。比如根據1.2.2節的分析，1.1.3所實現起泡排序bublesort1A()算法的時間復雜度應為T(n)=δ(n²)，故該算法即屬于此類。當然，以上所介紹的線性時間復雜度算法，也屬于多項式時間復雜度算法的特例，其中線性多項式f(n)=n的次數為1。

在算法復雜度理論中，多項式時間復雜度被視作一個具有特殊意義的復雜度級別。多項式級的運行時間成本，在實際應用中一般被認為是可接受的或可忍受的。某問題若存在一個復雜度在此范圍以內的算法，則稱該問題是可有效求解的或易解的(tractable)。

請注意，這里僅要求多項式的次數為一個正的常數，而并未對其最大取值范圍設置任何具體上限，故實際上該復雜度級別涵蓋了很大的一類算法。比如，從理論上講，復雜度分別為δ(n²)和δ(n²⁰¹²)算法都同屬此類，盡管二者實際的計算效率有天壤之別。之所以如此，是因為相對于以下的指數級復雜度，二者之間不超過多項式規模的差異只是小巫見大巫。

指數δ(2ⁿ)

• 問題與算法

考查如下問題：在禁止超過1位的移位運算的前提下，對任意非負整數n，計算冪2ⁿ。

_int64 power2BF_I(int n){ //冪函數2^n算法（蠻力迭代版）, n >= 0_int64 pow = 1; // O(1):累積器初始化為2^0while (0 < n --) //O(n):迭代n輪，每輪都pow <<= 1; //O(1):將累計器翻倍return pow; //O(1):返回累積器 } //O(n)=O(2^r)，r為輸入指數n的比特位數 代碼1.4 冪函數算法（蠻力迭代版）

• 復雜度

如代碼1.4所示的算法power2BF_I()由n輪迭代組成，各需做一次累乘和一次遞減，均屬于基本操作，故整個算法共需要δ(n)時間。若以輸入指數n的二進制位數r=1+「log₂n」作為輸入規模，則運行時間為δ(2^r)。稍后再1.4.3節我們將看到，該算法仍有巨大的改進空間。

一般地，凡運行時間可以表示和度量為T(n) = δ(aⁿ)形式的算法(a>1)，均屬于“指數時間復雜度算法”(exponential-time algorithm)。

• 從多項式到指數

從常數、對數、線性、平方到多項式時間復雜度，算法效率的差異還在可接受的范圍。然而在多項式與指數時間復雜度之間，卻有一道巨大的鴻溝。當問題規模較大后，指數復雜度算法的實際效率將急劇下降，計算時間之長很快就會達到讓人難以忍受的地步。因此通常認為，指數復雜度算法無法真正應用于實際問題中，它們不是有效算法，甚至不能稱作算法。相應地，不存在多項式復雜度算法的問題，也稱作難解的(intractable)問題。

需要注意的是，在問題規模不大的時候，指數復雜度反而可能在較長一段區間內均低于多項式復雜度。

復雜度層次

圖1.5 復雜度的典型層次：（1）~（7）δ(logn)、δ(√n)、δ(n)、δ(nlogn)、δ(n²)、δ(n³)、δ(2ⁿ)、

利用大δ記號，不僅可以定量地把我算法復雜度的主要部分，而且可以定性地由低到高將復雜度劃分為若干層次。

輸入規模

對算法復雜度的界定，都是相對于問題的輸入規模而言的。嚴格地講，所謂待計算問題的 輸入規模，應嚴格定義為“用以描述輸入所需的空間規模”。

(img-OynPKFiz-1622097373627)]

圖1.5 復雜度的典型層次：（1）~（7）δ(logn)、δ(√n)、δ(n)、δ(nlogn)、δ(n²)、δ(n³)、δ(2ⁿ)、

利用大δ記號，不僅可以定量地把我算法復雜度的主要部分，而且可以定性地由低到高將復雜度劃分為若干層次。

輸入規模

對算法復雜度的界定，都是相對于問題的輸入規模而言的。嚴格地講，所謂待計算問題的 輸入規模，應嚴格定義為“用以描述輸入所需的空間規模”。

結束寄語

今天的博文介紹就到此結束啦！下篇博文與各位再見面~

寫博不易，如蒙厚愛，賞個關注，一鍵三連~~點贊+評論+收藏🤞🤞🤞，感謝您的支持~~

總結

以上是生活随笔為你收集整理的【宝，我去读书了。读的什么书，给你的情书】《数据结构（c++）邓俊晖》-绪论篇的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。