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