《數(shù)據(jù)結(jié)構(gòu)》--算法ppt課件.ppt

《《數(shù)據(jù)結(jié)構(gòu)》--算法ppt課件.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、第2章算法計(jì)科系：王丹丹復(fù)習(xí)1、什么是數(shù)據(jù)結(jié)構(gòu)？2、本課程主要研究什么？3、什么是數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)？4、數(shù)據(jù)的邏輯結(jié)構(gòu)有哪幾種？存儲(chǔ)結(jié)構(gòu)有哪兩種形式？5、邏輯結(jié)構(gòu)與物理結(jié)構(gòu)間的關(guān)系？數(shù)據(jù)結(jié)構(gòu)主要研究什么？數(shù)據(jù)結(jié)構(gòu)是一門研究數(shù)據(jù)的各種邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)，以及對(duì)數(shù)據(jù)各種操作的課程。數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的操作(算法)：檢索、排序、插入、刪除、修改等線性結(jié)構(gòu)非線性結(jié)構(gòu)順序存儲(chǔ)鏈?zhǔn)酱鎯?chǔ)線性表?xiàng)ｊ?duì)樹形結(jié)構(gòu)圖形結(jié)構(gòu)本章內(nèi)容2.2數(shù)據(jù)結(jié)構(gòu)與算法關(guān)系2.3兩種算法的比較2.4算法定義2.5算法的特性2.6算法設(shè)計(jì)的要求2.7算法效率的度量2.8函數(shù)的漸近增長(zhǎng)2.9算

2、法時(shí)間復(fù)雜度2.10常見的時(shí)間復(fù)雜度2.11最壞情況和平均情況2.12算法空間復(fù)雜度2.1.3總結(jié)回顧要能回答的問題1、算法與程序的區(qū)別？2、算法的評(píng)價(jià)標(biāo)準(zhǔn)？3、什么是算法的時(shí)間復(fù)雜度？4、怎樣計(jì)算算法的時(shí)間復(fù)雜度？思考：寫一個(gè)求1+2+3+……+100結(jié)果的程序？2.4算法的定義算法(Algorithm)：對(duì)特定問題求解方法(步驟)的一種描述，是指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作。程序:計(jì)算機(jī)能夠理解和執(zhí)行的指令序列。算法與程序的區(qū)別和聯(lián)系算法的執(zhí)行是有窮的，而一個(gè)程序不一定滿足有窮性。例操作系統(tǒng)，只要整個(gè)系統(tǒng)不遭破壞，它將永遠(yuǎn)不會(huì)停止，即使沒有作業(yè)需

3、要處理，它仍處于動(dòng)態(tài)等待中。因此，操作系統(tǒng)不是一個(gè)算法。程序中的指令必須是機(jī)器可執(zhí)行的，而算法中的指令則無(wú)此限制。算法代表了對(duì)問題的解，而程序則是算法在計(jì)算機(jī)上的特定的實(shí)現(xiàn)。一個(gè)算法若用程序設(shè)計(jì)語(yǔ)言來描述，則它就是一個(gè)程序。2.5算法的特性輸入輸出一個(gè)算法應(yīng)該有零個(gè)或多個(gè)輸入，一個(gè)或多個(gè)輸出。有窮性一個(gè)算法必須在執(zhí)行有窮步之后結(jié)束。確定性算法中的每一步必須有確切的含義，無(wú)二義性。可行性算法中描述的每一步操作都可以通過已有的基本操作執(zhí)行有限次實(shí)現(xiàn)。2.6算法設(shè)計(jì)的要求評(píng)價(jià)一個(gè)好算法的幾個(gè)標(biāo)準(zhǔn)正確性(Correctness)：算法應(yīng)滿足具體問題的需求?？勺x性(Readab

4、ility)：算法應(yīng)容易供人閱讀和交流?？勺x性好的算法有助于對(duì)算法的理解和修改。健壯性(Robustness)：算法應(yīng)具有容錯(cuò)處理。當(dāng)輸入非法或錯(cuò)誤數(shù)據(jù)時(shí)，算法應(yīng)能適當(dāng)?shù)刈鞒龇磻?yīng)或進(jìn)行處理，而不會(huì)產(chǎn)生莫名其妙的輸出結(jié)果。效率與存儲(chǔ)量需求：效率指的是算法執(zhí)行的時(shí)間；存儲(chǔ)量需求指算法執(zhí)行過程中所需要的最大存儲(chǔ)空間。一般地，這兩者與問題的規(guī)模有關(guān)。算法的設(shè)計(jì)與分析算法的設(shè)計(jì)1、通過對(duì)問題進(jìn)行詳細(xì)地分析，抽象出相應(yīng)的數(shù)學(xué)模型；2、確定使用的數(shù)據(jù)結(jié)構(gòu)，并在此基礎(chǔ)上設(shè)計(jì)對(duì)此數(shù)據(jù)結(jié)構(gòu)實(shí)施各種操作的算法；3、描述算法（C語(yǔ)言中的函數(shù)）；4、選用某種語(yǔ)言將算法轉(zhuǎn)換成程序；5、調(diào)試并運(yùn)行

5、這些程序。算法的設(shè)計(jì)與分析算法的設(shè)計(jì)算法能用文字、高級(jí)語(yǔ)言、偽代碼進(jìn)行描述。案例按學(xué)號(hào)進(jìn)行順序查找NO=20020005的學(xué)生。設(shè)i=1，比較第i個(gè)元素的學(xué)號(hào)是否等于NO,如果相等，則查找成功，查找過程結(jié)束；否則，i++，繼續(xù)比較。學(xué)生信息表中，所有元素的學(xué)號(hào)都不等于NO，則查找失敗。算法設(shè)計(jì)的要求正確性1可讀性健壯性時(shí)間效率高和存儲(chǔ)量低234時(shí)間效率：算法的執(zhí)行時(shí)間。如何度量？思考：算法的優(yōu)劣？算法效率的度量方法事后統(tǒng)計(jì)方法：利用計(jì)算機(jī)計(jì)時(shí)器對(duì)不同算法編制的程序的運(yùn)行時(shí)間進(jìn)行比較。事前分析估計(jì)方法：計(jì)算機(jī)程序編制前，依據(jù)統(tǒng)計(jì)方法對(duì)算法進(jìn)行估算。2.7算法效率的度量方

6、法缺陷事后統(tǒng)計(jì)方法花費(fèi)大量的時(shí)間和精力依賴計(jì)算機(jī)硬件和軟件等環(huán)境因素算法的測(cè)試數(shù)據(jù)設(shè)計(jì)困難事先分析估算方法-運(yùn)行消耗時(shí)間算法采用的策略、方法01編譯產(chǎn)生的代碼質(zhì)量02機(jī)器執(zhí)行指令的速度04問題的輸入規(guī)模03因素算法好壞軟件支持輸入量的多少硬件性能第一種算法第二種算法執(zhí)行：1+（n+1）+n+1=2n+3次執(zhí)行：1+1+1=3次例子延伸算法的執(zhí)行次數(shù)：對(duì)于同樣輸入規(guī)模，要多于前面兩個(gè)。算法的執(zhí)行時(shí)間：隨著n的增加也將遠(yuǎn)遠(yuǎn)多于前兩種。測(cè)定運(yùn)行時(shí)間最可靠的方法：計(jì)算對(duì)運(yùn)行時(shí)間有消耗的基本操作的執(zhí)行次數(shù)。運(yùn)行時(shí)間與這個(gè)計(jì)數(shù)成正比！啟示同樣問題，輸入規(guī)模為n求和算法操作數(shù)量第一

7、種F(n)=n第二種F(n)=1第三種F(n)=n*n不同算法的操作數(shù)量對(duì)比隨著n值的越來越大，它們?cè)跁r(shí)間效率上的差異也就越來越大。2.8函數(shù)的漸近增長(zhǎng)觀察數(shù)據(jù)的特點(diǎn)？判斷：算法A和B哪個(gè)更好？函數(shù)的漸近增長(zhǎng)：給定兩個(gè)函數(shù)f(n)和g(n)，如果存在一個(gè)整數(shù)N，使得對(duì)于所有的n>N，f(n)總是比g(n)大，那么，我們說f(n)的增長(zhǎng)漸近快于g(n)?？梢院雎赃@些加法常數(shù)！2.8函數(shù)的漸近增長(zhǎng)與最高次項(xiàng)相乘的常數(shù)并不重要！2.8函數(shù)的漸近增長(zhǎng)最高次項(xiàng)的指數(shù)大的，函數(shù)隨著n的增長(zhǎng)，結(jié)果也會(huì)變得增長(zhǎng)特別快。2.8函數(shù)的漸近增長(zhǎng)判斷一個(gè)算法好壞，我們只通過