數據結構與算法講解(編輯修改稿)

　

【文章內容簡介】 算法的特征： ①有窮性、②確定性、③能行性、④輸入、⑤輸出 算法描述： ①自然語言；②程序設計語言；③類語言 ； 常用的算法設計方法： ①遞歸法（ Recursion）、②分治法 (Divideand Conquer)、 ③貪心法 (Greedy)、④動態規劃 (Dynamic Programming)、 ⑤搜索與遍歷、⑥回溯（ Backtracking）、⑦解空間局部搜索 ⑧近似算法 (Approximation)、⑨在線算法（ OnLine）等 二、 好的算法的標準 (Correctness) ? 正確性的含義：是指對于一切合法的輸入數據經有限時間或有限步后均可得到正確（滿足規格說明要求）的結果； ? 算法包括兩方面的內容： ① 解決問題的方法；② 實現這一方法的一系列指令 (語句、步驟 ) ? 算法的正確性證明：①需要一組相關的引理和定理，確認一個算法所使用的方法和公式的正確性； ②在證明一系列的語句確實做了符合規定的動作。 ? 算法的正確性的嚴格的形式化證明還未取得突破，還是一項令人生畏的工作。只有那些比較簡單的算法，其正確性才能被形式化證明。 二、 好的算法的標準 (Time Complexity) ?如何計算和比較算法的執行時間： ⑴實驗測量法（實際執行時間、執行指令的條數） 優點：精確 缺點： 必須先運行根據算法編制的的程序；所得的時間統計量依賴于計算機的硬件、軟件等環境因素，容易掩蓋算法本身的優劣。 二、 好的算法的標準 ⑵事前分析 (估計 )法 高級語言編寫的程序在計算機上運行時間取決于下列因素： ①依據的算法本身選擇何種策略 ②問題的規模（輸入的規模，輸入的大小）。如求素數問題 ③程序設計語言：算法的實現語言級別越高，執行效率越低 ④編譯程序產生的機器代碼的質量 ⑤及其執行指令的速度 ③④⑤表明用絕對的時間單位衡量一個算法的效率是不適合的 二、 好的算法的標準 ?算法的時間復雜性 ① 認為一個特定的算法執行時間 (運行工作量的大小 )，只依賴于問題的規模，即算法執行時間是問題規模的函數 ②由于算法的執行時間由組成算法的控制結構（順序、分支和循環）和基本操作的綜合效果，因此從算法中選擇對于研究問題來說是基本的操作（基本運算） ,把算法的基本操作的重復執行的次數作為算法的時間度量 ③通常，我們并不關心 T(n)的具體值，而是關心它的增長率 ,即T(n)隨問題規模 n（是一個整數）的增大的變化趨勢（界限） ④算法的復雜性定義 算法中基本操作重復執行的次數是問題規模 n的某個函數 f(n)，算法的時間度量記作 T（ n） = O（ f（ n））。它表示隨問題規模 n的增大，算法執行時間的增長率不會超過 f（ n），稱為算法的漸進時間復雜性，簡稱時間復雜性。 二、 好的算法的標準 (Space Complexity) ?算法的空間復雜性是指算法在執行過程中的存儲量需求 ?一個算法的存儲量需求除了存放算法本身所有的指令、常數、變量和輸入數據外，還包括對數據進行操作的工作單元和存儲實現計算所需信息的輔助空間 ?算法的存儲量需求與輸入的規模、表示方式、算法采用的數據結構、算法的設計以及輸入數據的性質有關 ?算法的執行的不同時刻，其空間需求可能是不同的 ?算法的空間復雜性是指算法在執行過程中的最大存儲量需求 ?空間復雜性的漸進表示 空間復雜度 T（ n） = O（ f（ n）） 其中， n為問題的輸入規模 二、 好的算法的標準 (Readability) ?可讀性好的算法有助于設計者和和他人閱讀、理解、修改和重用 ?晦澀難懂的算法不僅容易隱藏錯誤，而且還增加了閱讀 難度 ?可讀性好的算法，常常也具有簡單性 (Robustness) ?當輸入數據非法時，能作出適當的反應（如對輸入數據進行語法檢查，提出修改輸入建議并提供重新輸入的機會），避免異常出錯 （ Flexibility）、可重用性 (Reuseabale)和自適應性 (Adaptability)等 一、算法的時間復雜性 定義 設一個領域問題的輸入的規模為 n， D n是該領域問題的所有輸入集合，任意一個輸入 I∈ D n是 P(I)是 I 出現的概率， Σ I∈ D n P(I)=1， T(I)是（解決該領域問題的）算法在輸入 I 下所執行的基本運算的次數。 稱 E(n)= Σ I∈ D n {P(I)* T(I)}為該算法的期望復雜性（平均時間復雜性） 稱 W(n)=max I∈ D n { T(I)}為該算法的最壞時間復雜性 一、算法的時間復雜性 例 A是一個由 n個不同元素的實數數組，給出求其最大和最小元素的算法和時間復雜性 void SM(double A[], int n, double amp。max, double amp。min ) { max=min=A[0]。 for ( k=1。 kn。 k++ ){ if( A[k]max ) max=A[k]。 if ( A[k]min ) min=A[k]。 }} 容易看出，算法 SM對大小為 n 的數組需要 2（ n1）比較，算法 SM的基本運算是元素比較，則復雜性為 2（ n1） 一、算法的時間復雜性 例 A是一個由 n個不同元素的實數數組，給出確定給定實數 K是否在 A中的算法及其時間復雜性 int SK(double A[], int n, double K ) { int j=0。 while ( jn){ if ( A[j]==K ) break。 else j++。 } return j 。//若 j n，則 K在 A中，否則 (j=n) K不在 A中 } 一、算法的時間復雜性 算法 SK的基本運算是元素與 K 的比較 假定 q 表示 K 在 A 中的概率，有假設 K 等于 A 的每個元素有相 同的概率。令 D n={ I0, I1, …In1 , In }，其中 I j ( 0 ≤ j n ) 表示 K==A [j] 的任意輸入， In 表示 K 不是 A 中元素的任意一個輸 入，由上述說明有：當 0 ≤ j n 時， P(Ij)