




版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
算法及其基礎第1頁,課件共40頁,創作于2023年2月第一章算法及其基礎1.1引子1.2算法的基本概念1.3算法設計的一般過程1.4算法分析1.5相關基礎第2頁,課件共40頁,創作于2023年2月本章的要點與難點要點:
理解算法的概念。程序與算法的區別和聯系;理解算法設計的一般過程;掌握用C++/JAVA語言以及偽代碼描述算法的方法;掌握算法的計算復雜性概念及分析。難點:算法的計算復雜性(主要指時間復雜性)分析。第3頁,課件共40頁,創作于2023年2月1.1引子–排序問題排序問題描述:輸入:數字序列X=<a1,a2,…,an>輸出:一個排列X‘=<a‘1,a‘2,…,a‘n>,數字序列X和排列X‘之間為滿射或一一映射(即元素一一對應),并且有a‘1≤a‘2≤…≤a‘n(元素間非減序)。例如:輸入:8,2,4,9,3,6輸出:2,3,4,6,8,9排序方法:冒泡、插入、歸并、二叉樹、桶排序等。穩定的;選擇、Shell、堆、快速、組合排序等,不穩定的。第4頁,課件共40頁,創作于2023年2月1.1引子–插入排序原理:通過構建有序序列,對于未排序數據,在已排序序列中從后向前掃描,找到相應位置并插入。偽代碼:INSERTION-SORT(A,n)//A[1..n]forj=2tondokey=A[j]i=j-1
whilei>0andA[i]>keydoA[i+1]=A[i]i=i-1A[i+1]=key第5頁,課件共40頁,創作于2023年2月1.1引子–插入排序示例:第6頁,課件共40頁,創作于2023年2月1.1引子–插入排序證明–基于循環不變式(LoopInvariant):循環不變式:在每次循環迭代之前,子數組A[1..j-1]已包含了最初位于A[1..j-1]、但已排好序的各個元素。初始化:第一輪迭代之前(即j=2),子數組A[1..j-1](即A[1])顯然保持了循環不變式;保持:假設第j次迭代之前循環不變式為真。該算法的第j次操作只是將A[j]與已有序的A[1..j-1]中的元素進行比較,找到合適位置并插入。j+1次迭代之前,很顯然A[1..(j+1)-1]也保持了循環不變式;終止:j=n+1時,顯然A[1..(n+1)-1](即A[1..n])已包含了最初位于A[1..n]、且已排好序的各個元素。第7頁,課件共40頁,創作于2023年2月1.1引子–插入排序運行時間分析:最壞情況:T(n)=O(n2)。,算術級數。已非升序排序;平均情況:T(n)=O(n2)。
,算術級數;最好情況:T(n)=O(n)。,已升序排序。第8頁,課件共40頁,創作于2023年2月1.1引子–歸并排序原理:基于分而治之思想,遞歸地把待排序序列分解為若干子序列并進行排序,再把已排序的子序列合并為整體有序序列,最終實現全序列的有序。偽代碼:MERGE-SORT(A,low,high)//A[1..n]iflow<highthenmid=(low+high)/2MERGE-SORT(A,low,mid)MERGE-SORT(A,mid+1,high)MERGE(A,low,mid,high)第9頁,課件共40頁,創作于2023年2月1.1引子–歸并排序示例MERGE-SORT:第10頁,課件共40頁,創作于2023年2月1.1引子–歸并排序(MERGE)MERGE:第11頁,課件共40頁,創作于2023年2月1.1引子–歸并排序證明:可以嘗試采用循環不變式自行證明,這里略。第12頁,課件共40頁,創作于2023年2月1.1引子–歸并排序運行時間分析:第13頁,課件共40頁,創作于2023年2月算法(Algorithm):對于計算機科學來說,算法指的是對特定問題求解步驟的一種描述,是若干條指令的有窮序列。
算法的特性:輸入(0個或多個)、輸出(至少1個)、確定性(無歧義)、有限性、可行性。描述方式:自然語言、圖形、程序設計語言、偽代碼本書采用了面向對象程序設計語言C++,講授時采用偽代碼。算法與程序的區別?1.2算法的基本概念–算法第14頁,課件共40頁,創作于2023年2月程序(Program)程序是算法用某種程序設計語言的具體實現;程序可以不滿足算法的性質(4)。例如:操作系統是一個在無限循環中執行的程序,因而其不是一個算法;操作系統的各種任務:可看成是單獨的問題,每一個問題由操作系統中的一個子程序通過特定的算法來實現。1.2算法的基本概念–程序第15頁,課件共40頁,創作于2023年2月會場安排問題、單源最短路徑、哈夫曼編碼、最小生成樹排序與查找、循環賽日程表最長公共子序列、矩陣連乘、凸多邊形最優三角剖分、加工順序等N后、最大團、圖的m著色0-1背包、TSP、布線問題等等1.2算法的基本概念–經典問題第16頁,課件共40頁,創作于2023年2月1.2算法的基本概念–拼圖游戲第17頁,課件共40頁,創作于2023年2月在n×n格的棋盤上放置彼此不受攻擊的n個皇后:按照國際象棋的規則,皇后可以攻擊與之處在同一行或同一列或同一斜線上的棋子;n后問題等價于在n×n格的棋盤上放置n個皇后,任何2個皇后不放在同一行或同一列或同一斜線上。1234567812345678QQQQQQQQ1.2算法的基本概念–N后問題第18頁,課件共40頁,創作于2023年2月1.2算法的基本概念–0-1背包問題第19頁,課件共40頁,創作于2023年2月起點
XXXXXXXXXXXXXXXXXXXX終點XXXXX1.2算法的基本概念–布線問題第20頁,課件共40頁,創作于2023年2月1.3算法設計的一般過程第21頁,課件共40頁,創作于2023年2月算法復雜性(亦稱算法復雜度)為算法運行時所需計算機資源的度量:時間復雜性(影響因素包括問題規模n、輸入序列I、算法本身A):T(n,I,A)T(n)空間復雜性(影響因素包括輸入輸出數據IO、輔助變量V、算法本身A):S(IO,V,A)S(V)很顯然:算法所需資源越多,算法的復雜性就越高;算法所需資源越少,算法的復雜性就越低。1.4算法分析–算法復雜性第22頁,課件共40頁,創作于2023年2月算法分析:對算法的時間復雜性和空間復雜性進行分析,這里主要還是指對算法的時間復雜性的分析。方法:事后統計和事前分析算法分析的意義:算法設計:復雜性盡可能的低;算法選用:選擇復雜性最低的算法;算法改進:算法分析有助于算法的改進。1.4算法分析第23頁,課件共40頁,創作于2023年2月影響算法運行時間的因素(除算法本身外):機器;采用語言及編譯程序;編程能力等。算法分析無需具體時間(精確或近似):針對同一問題不同算法的比較,相對而非絕對;應該獨立于機器及實現語言;無論科技如何發展,其運行時間的測度應始終成立;關心的是大的問題規模時的運行情況。漸近復雜性1.4算法分析–第24頁,課件共40頁,創作于2023年2月算法漸近復雜性態:設算法的運行時間為T(n),如果存在T*(n),使得
就稱T*(n)為算法的漸近性態或漸近時間復雜性。1.4算法分析–算法漸近復雜性態?第25頁,課件共40頁,創作于2023年2月假設算法A的運行時間表達式為T1(n):
T1(n)=30n4+20n3+40n2+46n+100
T*1(n)≈n4(階)假設算法B的運行時間表達式為T2(n):
T2(n)=1000n3+50n2+78n+10
T*2(n)≈n3(階)1.4算法分析–算法漸近復雜性態示例第26頁,課件共40頁,創作于2023年2月1.4算法分析–幾類階的增長趨勢nLog2nnnlog2nn2n32nn!103.3103.3*101021031033.6*1061026.61026.6*1021041061.3*10309.3*10157103101031.0*1041061091.1*103014*102567增長趨勢:1個基本操作花1ns=10-6秒1年=31536000秒=3.15*107秒第27頁,課件共40頁,創作于2023年2月漸近意義下的記號:O、Ω、Θ漸近上界-O(bigo)漸近下界-Ω(bigω)漸近精確界-Θ(bigθ)o、ω和θ1.4算法分析–漸近復雜性記號第28頁,課件共40頁,創作于2023年2月漸近上界-O(bigo):設f(N)和g(N)是定義在正數集上的正函數,下同。定義:如果存在正的常數C和自然數N0,使得當NN0時有f(N)Cg(N),則稱函數f(N)當N充分大時上有界,且g(N)是它的一個上界,記為f(N)=O(g(N))。即f(N)的階不高于g(N)的階。求T(n)=10n+4的漸近上界O:O(n)1.4算法分析–漸近上界第29頁,課件共40頁,創作于2023年2月根據O的定義,容易證明它有如下運算規則:
(1)O(f)+O(g)=O(max(f,g));
(2)O(f)+O(g)=O(f+g);
(3)O(f)O(g)=O(fg);
(4)如g(N)=O(f(N)),則(f)+O(g)=O(f);
(5)O(cf(N))=O(f(N)),其中c是一個正的常數;
(6)f=O(f)。1.4算法分析–漸近上界O運算規則第30頁,課件共40頁,創作于2023年2月常見的幾類算法復雜性:O(1):常數階;O(log2n),O(nlog2n):對數階;O(n),O(n2),O(n3),…,O(nm):多項式階。多項式時間算法;O(2n),O(n!),O(nn):指數階。指數時間算法。幾類復雜性之間的關系:O(1)<O(log2n)<O(n)<O(nlog2n)<O(n)<O(n2)<O(n3)<…<O(nm)<O(2n)<O(n!)<O(nn)1.4算法分析–常見幾類復雜性第31頁,課件共40頁,創作于2023年2月Ω(bigomega):如存在正的常數c和自然數n0,使得當nn0時有f(n)cg(n),則稱函數f(n)當n充分大時下有界,且g(n)是它的一個下界,記為f(N)=Ω(g(n))。即f(n)的階不低于g(n)的階。Θ(bigtheta):如存在正的常數c1,c2和自然數n0,使得當nn0時,有c1g(n)f(n)c2g(n),則稱g(n)和f(n)同階。o、ω和θ與O、Ω和Θ。1.4算法分析–漸近復雜性記號2第32頁,課件共40頁,創作于2023年2月求T(n)=30n4+20n3+40n2+46n+100的漸近下界Ω:Ω(n4)求T(n)=20n2+8n+10的漸近精確界Θ:Θ(n2)求T(n)=amnm+am-1nm-1+…+a1n+a0的漸近上界O、下界Ω和精確界Θ:O(nm)、Ω(nm)和Θ(nm)1.4算法分析–漸近界示例第33頁,課件共40頁,創作于2023年2月1.4算法分析–漸近界示例第34頁,課件共40頁,創作于2023年2月非遞歸算法:順序語句:各語句計算時間相加;選擇語句:條件判定語句以及各分支中語句計算時間的較大者;循環語句:循環體內計算時間*循環次數,還需考慮循環判定條件;對于嵌套循環:循環體內計算時間*所有循環次數。1.4
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經權益所有人同意不得將文件中的內容挪作商業或盈利用途。
- 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 中國房產代理行業市場深度分析及發展前景預測報告(2020-2025年)
- 中國手機移動搜索行業市場深度評估及投資戰略規劃報告
- 2024-2030全球叉車維修升降機行業調研及趨勢分析報告
- 中國快卸銷行業市場調研及未來發展趨勢預測報告
- 2024年全球及中國伺服電機維修行業頭部企業市場占有率及排名調研報告
- 2025年中國油灰刀行業發展前景預測及投資方向研究報告
- 中國醫藥批發市場調查研究及行業投資潛力預測報告
- 2025年中國礬土水泥行業市場發展監測及投資戰略咨詢報告
- 2021-2026年中國預制構件行業發展監測及投資戰略規劃研究報告
- 中國真空泵制造行業市場深度分析及投資戰略規劃研究報告
- 2021年中國美術學院輔導員招聘考試題庫及答案解析
- 初中道德與法治學科教學經驗交流
- 申辦出入境證件的函
- 安全評估收費指導意見
- DB34-T 4289-2022城鎮檢查井蓋安裝管理技術規程
- 年產3萬噸硫酸鉀,1.8萬噸副產工業鹽項目建設可行性研究報告
- 貴州省建筑與裝飾工程計價定額(2023版)
- 發證機關所在地區代碼表
- 征地補償數據庫建設技術方案
- 水下封底混凝土計算及施工
- YY∕T 1784-2021 血氣分析儀
評論
0/150
提交評論