一講算法概述

算法設(shè)計與分析曾華琳

2014.秋算法是計算機科學(xué)的靈魂“計算機科學(xué)的研究就是算法的研究”Turing獎獲得者，算法大師DonaldE.Knuth到2008年底為止，55名圖靈獎獲得者中，因算法方面的貢獻而獲獎的有30多個。算法的研究對推動計算機科學(xué)發(fā)展起著至關(guān)重要的作用。練內(nèi)功。不要只花功夫?qū)W習(xí)各種流行的編程語言和工具，以及一些公司招聘廣告上要求的科目。要把數(shù)據(jù)結(jié)構(gòu)、算法、數(shù)據(jù)庫、操作系統(tǒng)原理、計算機體系結(jié)構(gòu)、計算機網(wǎng)絡(luò)，離散數(shù)學(xué)等基礎(chǔ)課程學(xué)好。《李開復(fù)給中國計算機系大學(xué)生的7點建議》課程性質(zhì)、目的與任務(wù)“算法設(shè)計與分析”是智能科學(xué)與技術(shù)專業(yè)一門重點專業(yè)基礎(chǔ)課程，也是學(xué)科核心專業(yè)基礎(chǔ)課程。本課程主要介紹算法設(shè)計與分析的基本方法以及算法復(fù)雜性理論基礎(chǔ)。通過本課程的學(xué)習(xí)，要求學(xué)生理解并熟練掌握遞歸與分治法、貪心法、動態(tài)規(guī)劃方法、回溯法、分支定界法，以及高級圖論算法、線性規(guī)劃算法等，理解并掌握算法復(fù)雜性的分析方法、NP完全性理論基礎(chǔ)等計算復(fù)雜性的基本知識及完備性證明概要。計算機算法設(shè)計與分析（第2版）王曉東編著電子工業(yè)出版社參考教材書名：《算法導(dǎo)論》(第2版)著者：ThomasH.Cormen,CharlesE.Leiserson,RonaldL.Rivest,CliffordStein譯者：潘金貴,顧鐵成等出版社：機械工業(yè)出版社出版時間：2006年9月定價：85元“計算機算法的圣經(jīng)”延伸教材：《TheArtofComputerProgramming》,DonaldE,Knuth，1974,TuringPrizeBillGates：“如果你認為你是一名真正優(yōu)秀的程序員請讀Knuth的《計算機程序設(shè)計藝術(shù)》，如果你能讀懂整套書的話請給我發(fā)一份你的簡歷。”李開復(fù)：“不妨試試DonaldKnuth的ArtofComputerProgramming里的題目，如果你能夠解決其中的大部分題目，就說明你在算法方面的功力不錯了?！笨己诵问狡谀?期中)考試(閉卷)：60%課堂作業(yè)+上機作業(yè)：30%出勤+課堂紀律：10%課程要求布置的作業(yè)一定要完成必須獨立完成，盡你的能力，需要思考有能力的同學(xué)可以完成附加的，或者課后的所有作業(yè)希望能自覺組織一些討論小組課件下載地址

密碼：2014Email：第1章算法概述學(xué)習(xí)要點:

理解算法的概念。理解什么是程序，程序與算法的區(qū)別和內(nèi)在聯(lián)系。掌握算法的計算復(fù)雜性概念。掌握算法漸近復(fù)雜性的數(shù)學(xué)表述。掌握用C++語言描述算法的方法。程序=數(shù)據(jù)結(jié)構(gòu)+算法Turing獎獲得者，Pascal之父NiklausWirth問題……解題問題…解題在n×n格的棋盤上放置彼此不受攻擊的n個皇后。按照國際象棋的規(guī)則，皇后可以攻擊與之處在同一行或同一列或同一斜線上的棋子。n后問題等價于在n×n格的棋盤上放置n個皇后，任何2個皇后不放在同一行或同一列或同一斜線上。f(x)目標函數(shù)S解空間x∈S約束條件具體到抽象的映射為一個實際問題建立數(shù)學(xué)模型以方便求解計算機程序性能以及資源使用情況的理論性分析為什么要研究算法和性能？算法幫助我們理解“可測量性”（scalability）性能，總能在“可行”（feasible）與“不可行”（impossible）之間為我們劃分標準。數(shù)學(xué)化的算法，提供給我們一種方式，去說明和衡量一個程序的行為。性能，總能歸結(jié)于其他資源的利用Speedisfun！作為一種技術(shù)的算法如果計算無限快、存儲器都是免費的，那算法研究是否還需要？Yes！證明方案是正確的，可以給出正確的結(jié)果！Yes！希望自己的實現(xiàn)符合良好的軟件工程實際要求，采用最容易的實現(xiàn)方法！算法對計算機非常重要，類比硬件與軟件的不同，算法的迥異帶來的意義可能更為明顯！算法與程序算法(Algorithm)算法是指解決問題的一種方法或一個過程。算法是若干指令的有窮序列，滿足性質(zhì)：(1)輸入：有外部提供的量作為算法的輸入。(2)輸出：算法產(chǎn)生至少一個量作為輸出。(3)確定性：組成算法的每條指令是清晰，無歧義的。(4)有限性：算法中每條指令的執(zhí)行次數(shù)是有限的，執(zhí)行每條指令的時間也是有限的。程序(Program)程序是算法用某種程序設(shè)計語言的具體實現(xiàn)。程序可以不滿足算法的性質(zhì)(4)。例如操作系統(tǒng)，是一個在無限循環(huán)中執(zhí)行的程序，因而不是一個算法。操作系統(tǒng)的各種任務(wù)可看成是單獨的問題，每一個問題由操作系統(tǒng)中的一個子程序通過特定的算法來實現(xiàn)。該子程序得到輸出結(jié)果后便終止。問題求解(ProblemSolving)證明正確性分析算法設(shè)計程序理解問題精確解或近似解選擇數(shù)據(jù)結(jié)構(gòu)算法設(shè)計策略設(shè)計算法一個例子分析算法運行時間Runningtime運行時間取決于輸入，一個已經(jīng)有序的序列更容易排序輸入數(shù)據(jù)規(guī)模影響著運行時間，因為短序列數(shù)據(jù)比長序列數(shù)據(jù)運行得快。我們追求的是運行時間的上界，因為我們需要一個保證時間。幾種分析方法最差情況:(通常發(fā)生)?T(n)=maximumtimeofalgorithmonanyinputofsizen.平均情況:(有時發(fā)生)?T(n)=expectedtimeofalgorithmoverallinputsofsizen.?Needassumptionofstatisticaldistributionofinputs.最優(yōu)情況:(偽造的)?Cheatwithaslowalgorithmthatworksfastonsomeinput.與機器無關(guān)的運行時間插入排序的最差時間是多少??取決于計算機的運行速度:?相對速度(onthesamemachine),?絕對速度(ondifferentmachines).假設(shè):?忽略與機器相關(guān)的所有限制?只關(guān)注增長率：growthofT(n)asn→∞.“Asymptotic漸近Analysis”分析算法1.算法分析是指對一個算法所需要的資源進行預(yù)測；資源包括：時間和空間軟件和硬件輸入數(shù)據(jù)規(guī)模和運行時間兩種分析算法的方法：:

直接分析與實驗比較對于一個問題，分析幾個候選的算法，選擇一個最有效的算法。找出不止一個候選算法，通常都要去掉幾個較差的算法。分析算法分析算法

空間資源已經(jīng)不是問題，分析一個算法，主要考慮算法的計算時間。插入排序算法分析InsertSort(A)1for

j←2to

length[A]2do

key←A[j]3//InsertA[j]intothesortedA[1..j-1]4i←j-15while

i>0andA[i]

>key

do6A[i+1]←A[i]7i←i-18A[i+1]←key

正確性分析利用歸納法證明初始步歸納步終止步InsertSort(A)1for

j←2to

length[A]2do

key←A[j]3//InsertA[j]intothesortedA[1..j-1]4i←j-15while

i>0andA[i]

>key

do6A[i+1]←A[i]7i←i-18A[i+1]←key

InsertSort(A)1for

j←2to

length[A]2do

key←A[j]3//InsertA[j]intothesortedA[1..j-1]4i←j-15while

i>0andA[i]

>key

do6A[i+1]←A[i]7i←i-18A[i+1]←key

算法效率分析Costtimes約定：在算法偽代碼中，執(zhí)行一行代碼僅花常數(shù)時間。第2行花費常數(shù)時間tj表示在for循環(huán)的迭代j中，while循環(huán)的次數(shù)。把算法執(zhí)行每行的次數(shù)與執(zhí)行每行所需要的時間相乘，然后把所有的時間求和：

5whilei>0andA[i]

>keydo6A[i+1]←A[i]7i←i-1最好、最差與平均情況nT(n)nBest-caseAverage-caseWorst-casePseudocode(偽代碼)conventions(約定）程序=數(shù)據(jù)結(jié)構(gòu)+算法算法是程序背后的思想，是程序的核心程序的本質(zhì)是算法，是算法的具體體現(xiàn)。描述一個