算法引論ppt課件(已修改)
2025-05-11 03:59 本頁面
【正文】 南京理工大學 算法設(shè)計與分析 Algorithm Design and Analysis 孫廷凱 南京理工大學 課程內(nèi)容 (32學時 ) ? 常用的算法 設(shè)計 策略 (包括分治策略、動態(tài)規(guī)劃、貪心策略、回溯法、隨機算法等 ) ? 算法復(fù)雜度 分析 方法 (計算迭代次數(shù)、使用遞歸方程、頻度分析等 ) 南京理工大學 課程要求 ? 掌握常用的算法設(shè)計策略、算法復(fù)雜度分析方法 ? 授課方式：講授 ? 考核方式： 南京理工大學 教材 ? 《 算法設(shè)計技巧與分析 》 ， M. H. Alsuwaiyel著 , 電子工業(yè)出版社，吳偉昶等譯， 2022 南京理工大學 相關(guān)參考文獻 ? Algorithm Design Techniques and Analysis, M. H. Alsuwaiyel. (影印本 ). 電子工業(yè)出版社 . 2022 ? 算法導論 (第 2版 )， Thomas H. Cormen等著，潘金貴等譯，機械工業(yè)出版社， 2022. ? 計算機算法設(shè)計與分析 (第 3版 ), 王曉東 , 電子工業(yè)出版社 , 2022. ? 算法設(shè)計與分析，王紅梅編著， 清華大學出版社， 2022. 南京理工大學 1 算法引論 ? 歷史背景 ? 算法復(fù)雜度與漸近分析方法 ? 如何估計算法的復(fù)雜度 ? 算法復(fù)雜度分析的意義 南京理工大學 歷史背景 ? 階段 1：二十世紀 30年代，能否使用一個有效的過程來求解一個問題 (相當于現(xiàn)在算法的概念 )一直是人們所關(guān)注的。當時的焦點是將問題進行分類：可解或是不可解。關(guān)注問題是否可以求解的領(lǐng)域稱為 可計算理論 (putability theory or theory of putation)。出現(xiàn)了一系列的計算模型，例如： calculus of Church、 Post machines of Post、 Turing machines of Turing、RAM model of putation。 ? 階段 2：隨著數(shù)字計算機的出現(xiàn)，人們越來越關(guān)注于那些可求解的問題。一開始，人們滿足于能夠在一定的時間內(nèi)解決一個特定的問題，而不去關(guān)注所需要的資源。慢慢地，人們需要考慮在有限資源的條件下高效地解決問題。這就導致了 計算復(fù)雜度(putational plexity)這一新學科的誕生。在這個領(lǐng)域，主要是研究解決可求解問題時所需要的資源，主要是時間和空間復(fù)雜性。有時候，其他的資源也需要考慮，例如，通信代價、需要使用的處理器的個數(shù) (使用并行計算模型 )等等。 南京理工大學 引例：搜索問題 ? 給定已經(jīng)排好序 (不妨假設(shè)為非降序 )的 n個元素A[1…n] , 現(xiàn)在要判定一個給定的元素 x是否在此數(shù)組中出現(xiàn)。 – 方法 1：順序搜索 – 方法 2：二分搜索 南京理工大學 二分搜索算法 輸入：非降序排列的數(shù)組 A[1…n] 和元素 x 輸出：如果 x=A[j], 1 ?j ?n,則輸出 j,否則輸出 0. 1. low←1。 high ←n。 j←0 2. while(low ?high) and (j=0) 3. mid ← ?( low+high)/2? 4. if x=A[mid] then j ←mid 5. else if xA[mid] then high ←mid 1 6. else low ←mid+1 7. end while 8. return j 南京理工大學 分析 ? 最好情形：比較 1次 ? 最壞情形：比較 ?logn?+1次 – 每次循環(huán)都要拋棄一些元素，例如第二次循環(huán)時，剩余元素為A[1…mid 1]或 A[mid+1…n] ，不妨設(shè)為 A[mid+1…n] ，則剩余的元素個數(shù)是 ?n/2? – 第 j次 while循環(huán)時，剩余元素的個數(shù)是 ?n/2j1? – 或者找到 x，或者程序在子序列長度達到 1時終止搜索 , 此時 ?n/2j1?=1 ? 1 ? n/2j1 2 ? 2j1 ?n 2j ?lognj?logn+1?j=?logn?+1 南京理工大學 算法及其性質(zhì) ? 算法是對問題求解過程的準確描述，由有限條指令組成，這些指
教學課件相關(guān)推薦
鄂ICP備17016276號-1