1、數(shù)據(jù)結(jié)構(gòu)引言課件1數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)引言課件22聯(lián)系方式聯(lián)系方式 陳玉泉：陳玉泉： chen- C(課程網(wǎng)站課程網(wǎng)站)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)B 電院樓群電院樓群3-525數(shù)據(jù)結(jié)構(gòu)引言課件3教材教材 教科書教科書1） 數(shù)據(jù)結(jié)構(gòu)：思想與實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)：思想與實(shí)現(xiàn)，翁惠玉、俞勇，高等教育出版社，翁惠玉、俞勇，高等教育出版社，2009.82） 數(shù)據(jù)結(jié)構(gòu)：題解與拓展數(shù)據(jù)結(jié)構(gòu)：題解與拓展，翁惠玉、俞勇，高等教育出版社，翁惠玉、俞勇，高等教育出版社，2011.8參考書：參考書：數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版），嚴(yán)蔚敏、吳偉民，清華大學(xué)出版社，語(yǔ)言版），嚴(yán)蔚敏、吳偉民，清華大學(xué)出版社，1997.4數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)

2、結(jié)構(gòu)與算法（C+），竇延平等，上海交通大學(xué)出版社，），竇延平等，上海交通大學(xué)出版社，2005.5算法導(dǎo)論算法導(dǎo)論，Thomas H.Charles著，潘金貴譯，機(jī)械工業(yè)出版社，著，潘金貴譯，機(jī)械工業(yè)出版社，2006.9算法之道算法之道，鄒恒明，機(jī)械工業(yè)出版社，鄒恒明，機(jī)械工業(yè)出版社，2012.4數(shù)據(jù)結(jié)構(gòu)引言課件44課程說(shuō)明 講授內(nèi)容：講授內(nèi)容： 32學(xué)時(shí)安排學(xué)時(shí)安排.doc 作業(yè)：作業(yè)： Email提交作業(yè)提交作業(yè)數(shù)據(jù)結(jié)構(gòu)引言課件5第一章第一章 引言引言 什么是數(shù)據(jù)結(jié)構(gòu)什么是數(shù)據(jù)結(jié)構(gòu) 算法分析算法分析 面向?qū)ο蟮臄?shù)據(jù)結(jié)構(gòu)面向?qū)ο蟮臄?shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)引言課件6什么是數(shù)據(jù)結(jié)構(gòu)什么是數(shù)據(jù)結(jié)構(gòu) 沒(méi)有標(biāo)準(zhǔn)

3、的定義，但有共識(shí)沒(méi)有標(biāo)準(zhǔn)的定義，但有共識(shí) 數(shù)據(jù)結(jié)構(gòu)：通過(guò)抽象的方法研究一組有特定數(shù)據(jù)結(jié)構(gòu)：通過(guò)抽象的方法研究一組有特定關(guān)系的數(shù)據(jù)的存儲(chǔ)與處理關(guān)系的數(shù)據(jù)的存儲(chǔ)與處理 數(shù)據(jù)結(jié)構(gòu)的研究?jī)?nèi)容：數(shù)據(jù)結(jié)構(gòu)的研究?jī)?nèi)容：數(shù)據(jù)之間的邏輯關(guān)系，以及這種關(guān)系對(duì)應(yīng)的操作數(shù)據(jù)之間的邏輯關(guān)系，以及這種關(guān)系對(duì)應(yīng)的操作如何存儲(chǔ)某種邏輯關(guān)系（存儲(chǔ)實(shí)現(xiàn)）如何存儲(chǔ)某種邏輯關(guān)系（存儲(chǔ)實(shí)現(xiàn)）在這種存儲(chǔ)模式下，關(guān)系的操作是如何實(shí)現(xiàn)的在這種存儲(chǔ)模式下，關(guān)系的操作是如何實(shí)現(xiàn)的（運(yùn)算實(shí)現(xiàn)）（運(yùn)算實(shí)現(xiàn)）數(shù)據(jù)結(jié)構(gòu)引言課件7數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu) 集合結(jié)構(gòu)：元素間的次序是任意的。元素集合結(jié)構(gòu)：元素間的次序是任意的。元素之間除了之間除了“屬于同

4、一集合屬于同一集合”的聯(lián)系外沒(méi)有的聯(lián)系外沒(méi)有其他的關(guān)系。其他的關(guān)系。 線性結(jié)構(gòu)：數(shù)據(jù)元素的有序序列。除了第線性結(jié)構(gòu)：數(shù)據(jù)元素的有序序列。除了第一個(gè)和最后一個(gè)元素外，其余元素都有一一個(gè)和最后一個(gè)元素外，其余元素都有一個(gè)前趨和一個(gè)后繼個(gè)前趨和一個(gè)后繼 樹(shù)形結(jié)構(gòu)：除了根元素外，每個(gè)節(jié)點(diǎn)有且樹(shù)形結(jié)構(gòu)：除了根元素外，每個(gè)節(jié)點(diǎn)有且僅有一個(gè)前趨，后繼數(shù)目不限僅有一個(gè)前趨，后繼數(shù)目不限 圖型結(jié)構(gòu)：每個(gè)元素的前趨和后繼數(shù)目都圖型結(jié)構(gòu)：每個(gè)元素的前趨和后繼數(shù)目都不限不限數(shù)據(jù)結(jié)構(gòu)引言課件8集合結(jié)構(gòu)集合結(jié)構(gòu)線性結(jié)構(gòu)線性結(jié)構(gòu)樹(shù)形結(jié)構(gòu)樹(shù)形結(jié)構(gòu)圖形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)引言課件9數(shù)據(jù)結(jié)構(gòu)的操作數(shù)據(jù)結(jié)構(gòu)的操作 創(chuàng)建：創(chuàng)建一個(gè)數(shù)

5、據(jù)結(jié)構(gòu)創(chuàng)建：創(chuàng)建一個(gè)數(shù)據(jù)結(jié)構(gòu) 清除：刪除數(shù)據(jù)結(jié)構(gòu)清除：刪除數(shù)據(jù)結(jié)構(gòu) 插入：在數(shù)據(jù)結(jié)構(gòu)指定的位置上插入一個(gè)新元素插入：在數(shù)據(jù)結(jié)構(gòu)指定的位置上插入一個(gè)新元素 刪除：將數(shù)據(jù)結(jié)構(gòu)中的某個(gè)元素刪去刪除：將數(shù)據(jù)結(jié)構(gòu)中的某個(gè)元素刪去 搜索：在數(shù)據(jù)結(jié)構(gòu)中搜索滿足特定條件的元素搜索：在數(shù)據(jù)結(jié)構(gòu)中搜索滿足特定條件的元素 更新：修改數(shù)據(jù)結(jié)構(gòu)中的某個(gè)元素的值更新：修改數(shù)據(jù)結(jié)構(gòu)中的某個(gè)元素的值 訪問(wèn)：訪問(wèn)數(shù)據(jù)結(jié)構(gòu)中的某個(gè)元素訪問(wèn)：訪問(wèn)數(shù)據(jù)結(jié)構(gòu)中的某個(gè)元素 遍歷：按照某種次序訪問(wèn)數(shù)據(jù)結(jié)構(gòu)中的每一元素，使每個(gè)遍歷：按照某種次序訪問(wèn)數(shù)據(jù)結(jié)構(gòu)中的每一元素，使每個(gè)元素恰好被訪問(wèn)一次元素恰好被訪問(wèn)一次 每一種數(shù)據(jù)結(jié)構(gòu)的特定操作每一

6、種數(shù)據(jù)結(jié)構(gòu)的特定操作數(shù)據(jù)結(jié)構(gòu)引言課件10數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)實(shí)現(xiàn) 包括兩個(gè)部分：包括兩個(gè)部分：數(shù)據(jù)元素的存儲(chǔ)數(shù)據(jù)元素的存儲(chǔ)數(shù)據(jù)元素之間的關(guān)系的存儲(chǔ)數(shù)據(jù)元素之間的關(guān)系的存儲(chǔ) 物理結(jié)構(gòu)由三個(gè)部分組成：物理結(jié)構(gòu)由三個(gè)部分組成：存儲(chǔ)結(jié)點(diǎn)，每個(gè)存儲(chǔ)結(jié)點(diǎn)存放一個(gè)數(shù)據(jù)元素；存儲(chǔ)結(jié)點(diǎn)，每個(gè)存儲(chǔ)結(jié)點(diǎn)存放一個(gè)數(shù)據(jù)元素；數(shù)據(jù)元素之間的關(guān)系的存儲(chǔ)，也就是邏輯結(jié)構(gòu)數(shù)據(jù)元素之間的關(guān)系的存儲(chǔ)，也就是邏輯結(jié)構(gòu)的機(jī)內(nèi)表示；的機(jī)內(nèi)表示；附加信息，便于運(yùn)算實(shí)現(xiàn)而設(shè)置的一些附加信息，便于運(yùn)算實(shí)現(xiàn)而設(shè)置的一些“啞結(jié)啞結(jié)點(diǎn)點(diǎn)”，如鏈表中的頭結(jié)點(diǎn)。，如鏈表中的頭結(jié)點(diǎn)。 數(shù)據(jù)結(jié)構(gòu)引言課件11基本的存儲(chǔ)方式基本的存儲(chǔ)方式 數(shù)據(jù)元素

7、的類型可以是各種各樣的，通數(shù)據(jù)元素的類型可以是各種各樣的，通常不會(huì)是簡(jiǎn)單的內(nèi)置類型，因此存儲(chǔ)結(jié)常不會(huì)是簡(jiǎn)單的內(nèi)置類型，因此存儲(chǔ)結(jié)點(diǎn)可以是一個(gè)結(jié)構(gòu)體類型的變量或?qū)ο簏c(diǎn)可以是一個(gè)結(jié)構(gòu)體類型的變量或?qū)ο?數(shù)據(jù)結(jié)構(gòu)主要討論關(guān)系的存儲(chǔ)。因此，數(shù)據(jù)結(jié)構(gòu)主要討論關(guān)系的存儲(chǔ)。因此，數(shù)據(jù)結(jié)構(gòu)主要采用泛型程序設(shè)計(jì)的思想數(shù)據(jù)結(jié)構(gòu)主要采用泛型程序設(shè)計(jì)的思想數(shù)據(jù)結(jié)構(gòu)引言課件12關(guān)系的存儲(chǔ)關(guān)系的存儲(chǔ)順序存儲(chǔ)：用存儲(chǔ)的位置表示元素之間的關(guān)系。順序存儲(chǔ)：用存儲(chǔ)的位置表示元素之間的關(guān)系。主要用數(shù)組實(shí)現(xiàn)。主要用數(shù)組實(shí)現(xiàn)。鏈接存儲(chǔ)：用指針顯式地指出元素之間的關(guān)系，鏈接存儲(chǔ)：用指針顯式地指出元素之間的關(guān)系，如單鏈表就是表示線性關(guān)系的

8、如單鏈表就是表示線性關(guān)系的哈希存儲(chǔ)方式：是專用于集合結(jié)構(gòu)的數(shù)據(jù)存放方哈希存儲(chǔ)方式：是專用于集合結(jié)構(gòu)的數(shù)據(jù)存放方式。在哈希存儲(chǔ)中，各個(gè)結(jié)點(diǎn)均勻地分布在一塊式。在哈希存儲(chǔ)中，各個(gè)結(jié)點(diǎn)均勻地分布在一塊連續(xù)的存儲(chǔ)區(qū)域中，用一個(gè)哈希函數(shù)將數(shù)據(jù)元素連續(xù)的存儲(chǔ)區(qū)域中，用一個(gè)哈希函數(shù)將數(shù)據(jù)元素和存儲(chǔ)位置關(guān)聯(lián)起來(lái)。和存儲(chǔ)位置關(guān)聯(lián)起來(lái)。索引存儲(chǔ)方式：所有的存儲(chǔ)結(jié)點(diǎn)按照生成的次序索引存儲(chǔ)方式：所有的存儲(chǔ)結(jié)點(diǎn)按照生成的次序連續(xù)存放。另外設(shè)置一個(gè)索引區(qū)域表示結(jié)點(diǎn)之間連續(xù)存放。另外設(shè)置一個(gè)索引區(qū)域表示結(jié)點(diǎn)之間的關(guān)系。的關(guān)系。 數(shù)據(jù)結(jié)構(gòu)引言課件13第一章第一章 引言引言 什么是數(shù)據(jù)結(jié)構(gòu)什么是數(shù)據(jù)結(jié)構(gòu) 算法分析算法分析 面向

9、對(duì)象的數(shù)據(jù)結(jié)構(gòu)面向?qū)ο蟮臄?shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)引言課件14算法分析算法分析 數(shù)據(jù)結(jié)構(gòu)是討論一組數(shù)據(jù)的處理問(wèn)題。數(shù)據(jù)結(jié)構(gòu)是討論一組數(shù)據(jù)的處理問(wèn)題。 每一種存儲(chǔ)方式下對(duì)應(yīng)的每一種操作的每一種存儲(chǔ)方式下對(duì)應(yīng)的每一種操作的實(shí)現(xiàn)都是一個(gè)算法實(shí)現(xiàn)都是一個(gè)算法 每種操作有多種實(shí)現(xiàn)方式每種操作有多種實(shí)現(xiàn)方式 如何評(píng)價(jià)這些算法的好壞如何評(píng)價(jià)這些算法的好壞數(shù)據(jù)結(jié)構(gòu)引言課件15算法的質(zhì)量評(píng)價(jià)算法的質(zhì)量評(píng)價(jià)正確性：算法應(yīng)能正確地實(shí)現(xiàn)預(yù)定的功能；正確性：算法應(yīng)能正確地實(shí)現(xiàn)預(yù)定的功能；易讀性：算法應(yīng)易于閱讀和理解，以便于調(diào)試、易讀性：算法應(yīng)易于閱讀和理解，以便于調(diào)試、修改和擴(kuò)充；修改和擴(kuò)充；健壯性：當(dāng)環(huán)境發(fā)生變化（如遇到非法輸

10、入）時(shí)，健壯性：當(dāng)環(huán)境發(fā)生變化（如遇到非法輸入）時(shí)，算法能適當(dāng)?shù)刈龀龇磻?yīng)或進(jìn)行處理，不會(huì)產(chǎn)生不算法能適當(dāng)?shù)刈龀龇磻?yīng)或進(jìn)行處理，不會(huì)產(chǎn)生不正確的運(yùn)算結(jié)果；正確的運(yùn)算結(jié)果；高效率：具有較高的時(shí)間和空間性能。高效率：具有較高的時(shí)間和空間性能。這四個(gè)指標(biāo)往往是互相沖突的，數(shù)據(jù)結(jié)構(gòu)主要考這四個(gè)指標(biāo)往往是互相沖突的，數(shù)據(jù)結(jié)構(gòu)主要考慮的是時(shí)空性能慮的是時(shí)空性能數(shù)據(jù)結(jié)構(gòu)引言課件16算法效率分析算法效率分析 如何確定一個(gè)算法是高效的算法就是分析如何確定一個(gè)算法是高效的算法就是分析該算法所需要的資源。算法的資源包括：該算法所需要的資源。算法的資源包括：時(shí)間：程序運(yùn)行所需要的時(shí)間。要運(yùn)行一年時(shí)間：程序運(yùn)行所需要的時(shí)

11、間。要運(yùn)行一年的算法是很難讓人接受的的算法是很難讓人接受的空間：程序運(yùn)行所需要的空間。需要幾個(gè)空間：程序運(yùn)行所需要的空間。需要幾個(gè)G G的的內(nèi)存的算法同樣也令人難以接受。內(nèi)存的算法同樣也令人難以接受。數(shù)據(jù)結(jié)構(gòu)引言課件17算法分析算法分析時(shí)間復(fù)雜度的概念時(shí)間復(fù)雜度的概念 算法運(yùn)算量的計(jì)算算法運(yùn)算量的計(jì)算漸進(jìn)表示法漸進(jìn)表示法時(shí)間復(fù)雜度的計(jì)算時(shí)間復(fù)雜度的計(jì)算算法的優(yōu)化算法的優(yōu)化空間復(fù)雜度的概念空間復(fù)雜度的概念 數(shù)據(jù)結(jié)構(gòu)引言課件18程序的運(yùn)行時(shí)間程序的運(yùn)行時(shí)間 影響運(yùn)行時(shí)間的因素影響運(yùn)行時(shí)間的因素問(wèn)題規(guī)模和輸入數(shù)據(jù)的分布問(wèn)題規(guī)模和輸入數(shù)據(jù)的分布編譯器生成的目標(biāo)代碼的質(zhì)量編譯器生成的目標(biāo)代碼的質(zhì)量計(jì)算機(jī)

12、系統(tǒng)的性能計(jì)算機(jī)系統(tǒng)的性能程序采用的算法的優(yōu)劣程序采用的算法的優(yōu)劣 關(guān)鍵是算法的優(yōu)劣關(guān)鍵是算法的優(yōu)劣數(shù)據(jù)結(jié)構(gòu)引言課件19有效算法的重要性有效算法的重要性計(jì)算機(jī)不是萬(wàn)能的，并非所有的算法，計(jì)算機(jī)都能夠計(jì)算計(jì)算機(jī)不是萬(wàn)能的，并非所有的算法，計(jì)算機(jī)都能夠計(jì)算出有用的結(jié)果。差的算法不一定有實(shí)際意義。如果一臺(tái)計(jì)出有用的結(jié)果。差的算法不一定有實(shí)際意義。如果一臺(tái)計(jì)算機(jī)算機(jī) 1 秒能處理秒能處理1000條指令，那么如果處理?xiàng)l指令，那么如果處理n個(gè)數(shù)據(jù)所需個(gè)數(shù)據(jù)所需執(zhí)行的指令數(shù)如表中的函數(shù)所示執(zhí)行的指令數(shù)如表中的函數(shù)所示時(shí)間函數(shù)時(shí)間函數(shù)n=20n=50n=100n=500n.02s.05s.1s.5snlogn

13、.09s.3s.6s4.5sn2.4s2.5s10s250sn38s2分分17分分35小時(shí)小時(shí)2n34分分?jǐn)?shù)據(jù)結(jié)構(gòu)引言課件20有效時(shí)間中能夠處理的數(shù)據(jù)量有效時(shí)間中能夠處理的數(shù)據(jù)量時(shí)間函數(shù)時(shí)間函數(shù)在在 1 秒內(nèi)秒內(nèi) 在在 1 分鐘內(nèi)分鐘內(nèi) 在在 1 小時(shí)小時(shí)n10006 * 1043.6 * 106nlogn14048932 * 105n2312441897n310391532n101521數(shù)據(jù)結(jié)構(gòu)引言課件21有效算法的重要性有效算法的重要性關(guān)鍵：提高算法的效率而不是提高機(jī)器的速度！關(guān)鍵：提高算法的效率而不是提高機(jī)器的速度！時(shí)間函數(shù)時(shí)間函數(shù)提速提速10倍前的求倍前的求解規(guī)模解規(guī)模提速提速10倍后

14、的倍后的求解規(guī)模求解規(guī)模ns110s1nlogns210s2n2S33.16s3n3S42.15s42ns5S5 + 3.3數(shù)據(jù)結(jié)構(gòu)引言課件22時(shí)間復(fù)雜度時(shí)間復(fù)雜度 算法的時(shí)間復(fù)雜度是一種抽象的度量，即運(yùn)算算法的時(shí)間復(fù)雜度是一種抽象的度量，即運(yùn)算量與問(wèn)題規(guī)模之間的關(guān)系。量與問(wèn)題規(guī)模之間的關(guān)系。 算法的時(shí)間復(fù)雜度也與被處理的數(shù)據(jù)分布有關(guān)算法的時(shí)間復(fù)雜度也與被處理的數(shù)據(jù)分布有關(guān) 算法的時(shí)間復(fù)雜度算法的時(shí)間復(fù)雜度最好情況的時(shí)間復(fù)雜度最好情況的時(shí)間復(fù)雜度最壞情況的時(shí)間復(fù)雜度最壞情況的時(shí)間復(fù)雜度平均情況的時(shí)間復(fù)雜度平均情況的時(shí)間復(fù)雜度 數(shù)據(jù)結(jié)構(gòu)引言課件23算法分析算法分析時(shí)間復(fù)雜度的概念時(shí)間復(fù)雜度的概念

15、 算法運(yùn)算量的計(jì)算算法運(yùn)算量的計(jì)算漸進(jìn)表示法漸進(jìn)表示法時(shí)間復(fù)雜度的計(jì)算時(shí)間復(fù)雜度的計(jì)算算法的優(yōu)化算法的優(yōu)化空間復(fù)雜度的概念空間復(fù)雜度的概念 數(shù)據(jù)結(jié)構(gòu)引言課件24算法運(yùn)算量的計(jì)算算法運(yùn)算量的計(jì)算根據(jù)問(wèn)題的特點(diǎn)合理地選擇一種或幾種根據(jù)問(wèn)題的特點(diǎn)合理地選擇一種或幾種操作作為操作作為“標(biāo)準(zhǔn)操作標(biāo)準(zhǔn)操作”，將標(biāo)準(zhǔn)操作作，將標(biāo)準(zhǔn)操作作為一個(gè)抽象的運(yùn)算單位；為一個(gè)抽象的運(yùn)算單位；確定每個(gè)算法在給定的輸入下共執(zhí)行了確定每個(gè)算法在給定的輸入下共執(zhí)行了多少次標(biāo)準(zhǔn)操作；并將它作為算法的計(jì)多少次標(biāo)準(zhǔn)操作；并將它作為算法的計(jì)算量。算量。數(shù)據(jù)結(jié)構(gòu)引言課件25實(shí)例實(shí)例 如果有一組正整數(shù)，存放在數(shù)組如果有一組正整數(shù)，存放在數(shù)

16、組arrayarray中，中，要求設(shè)計(jì)一個(gè)算法求數(shù)組中的最大值與要求設(shè)計(jì)一個(gè)算法求數(shù)組中的最大值與d d的乘積。的乘積。 數(shù)據(jù)結(jié)構(gòu)引言課件26算法一算法一int max1(int array, int size, int d)int max=0, i; for (i=0; i size ; +i) arrayi *= d; for (i=0; i max) max = arrayi; return max;算法二算法二int max2(int array, int size, int d)int max=0, i; for (i=0; i max) max = arrayi; return m

17、ax * d;數(shù)據(jù)結(jié)構(gòu)引言課件27運(yùn)算量的計(jì)算運(yùn)算量的計(jì)算 用乘法、賦值和條件判斷作為標(biāo)準(zhǔn)操作用乘法、賦值和條件判斷作為標(biāo)準(zhǔn)操作 設(shè)輸入的數(shù)組值為設(shè)輸入的數(shù)組值為1,2,3,d=41,2,3,d=4 Max1Max1：3 3次乘法，次乘法，1414次賦值，次賦值，1111次比較，次比較，共共2828次標(biāo)準(zhǔn)操作次標(biāo)準(zhǔn)操作 max2max2執(zhí)行了執(zhí)行了1 1次乘法，次乘法，7 7次賦值，次賦值，7 7次比較，次比較，共共1515次標(biāo)準(zhǔn)操作。次標(biāo)準(zhǔn)操作。 數(shù)據(jù)結(jié)構(gòu)引言課件28找出運(yùn)算量的函數(shù)找出運(yùn)算量的函數(shù) 如找出如找出max1max1的最壞情況下的運(yùn)行時(shí)間函數(shù)的最壞情況下的運(yùn)行時(shí)間函數(shù) 第一個(gè)第一

18、個(gè)forfor循環(huán)：循環(huán)：循環(huán)控制行中，表達(dá)式循環(huán)控制行中，表達(dá)式1 1執(zhí)行一次，表達(dá)式執(zhí)行一次，表達(dá)式2 2執(zhí)行執(zhí)行n+1n+1次，次，表達(dá)式表達(dá)式3 3執(zhí)行了執(zhí)行了n n次。次。每個(gè)循環(huán)周期執(zhí)行一次乘法、一次賦值。每個(gè)循環(huán)周期執(zhí)行一次乘法、一次賦值。總的運(yùn)算量為總的運(yùn)算量為1+(n+1)+n+n1+(n+1)+n+n* *2 = 4n+22 = 4n+2。 第二個(gè)循環(huán)：第二個(gè)循環(huán)：循環(huán)控制行中，表達(dá)式循環(huán)控制行中，表達(dá)式1 1執(zhí)行了一次，表達(dá)式執(zhí)行了一次，表達(dá)式2 2執(zhí)行了執(zhí)行了n+1n+1次，表達(dá)式次，表達(dá)式3 3執(zhí)行了執(zhí)行了n n次，次，每個(gè)循環(huán)周期執(zhí)行一次比較，一次賦值。每個(gè)循環(huán)周期

19、執(zhí)行一次比較，一次賦值。總運(yùn)算量為總運(yùn)算量為1+(n+1)+n+n1+(n+1)+n+n* *2 = 4n+22 = 4n+2。 max1max1在最壞情況下的總運(yùn)算量是在最壞情況下的總運(yùn)算量是8n+48n+4。 數(shù)據(jù)結(jié)構(gòu)引言課件29算法分析算法分析時(shí)間復(fù)雜度的概念時(shí)間復(fù)雜度的概念 算法運(yùn)算量的計(jì)算算法運(yùn)算量的計(jì)算漸進(jìn)表示法漸進(jìn)表示法時(shí)間復(fù)雜度的計(jì)算時(shí)間復(fù)雜度的計(jì)算算法的優(yōu)化算法的優(yōu)化時(shí)間復(fù)雜度的概念時(shí)間復(fù)雜度的概念 數(shù)據(jù)結(jié)構(gòu)引言課件30漸進(jìn)表示法漸進(jìn)表示法 算法的運(yùn)行時(shí)間函數(shù)可能是一個(gè)很復(fù)雜算法的運(yùn)行時(shí)間函數(shù)可能是一個(gè)很復(fù)雜的函數(shù)，如何比較這些函數(shù)并從中選取的函數(shù)，如何比較這些函數(shù)并從中選取

20、出一個(gè)好的算法呢？出一個(gè)好的算法呢？ 時(shí)間性能主要考慮的是問(wèn)題規(guī)模很大的時(shí)間性能主要考慮的是問(wèn)題規(guī)模很大的時(shí)候運(yùn)行時(shí)間隨問(wèn)題規(guī)模的變化規(guī)律時(shí)候運(yùn)行時(shí)間隨問(wèn)題規(guī)模的變化規(guī)律 漸進(jìn)表示法：不考慮具體的運(yùn)行時(shí)間函漸進(jìn)表示法：不考慮具體的運(yùn)行時(shí)間函數(shù)，只考慮運(yùn)行時(shí)間函數(shù)的數(shù)量級(jí)數(shù)，只考慮運(yùn)行時(shí)間函數(shù)的數(shù)量級(jí)數(shù)據(jù)結(jié)構(gòu)引言課件31漸進(jìn)表示法漸進(jìn)表示法 定義：定義：( (大大O) O) 如果存在正的常數(shù)如果存在正的常數(shù)c c和和N N0 0，滿足當(dāng)，滿足當(dāng)N=NN=N0 0時(shí)有時(shí)有T(N)= cF(N)T(N)=NN=N0 0時(shí)有時(shí)有T(N) cF(N)T(N) cF(N)，則，則T(N)T(N)是是(F(

21、N)(F(N)。 定義：定義：( (大大) ) 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)T(N)T(N)是是O(F(N)O(F(N)，并且，并且T(N)T(N)又是又是(F(N)(F(N)，則，則T(N)T(N)是是(F(N)(F(N)。 定義：定義：( (小小O) O) 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)T(N)T(N)是是O(F(N)O(F(N)，并且，并且T(N)T(N)不是不是 (F(N) (F(N)，則，則T(N)T(N)是是o(F(N)o(F(N)。數(shù)據(jù)結(jié)構(gòu)引言課件32大大O表示法實(shí)例表示法實(shí)例 設(shè)設(shè) T(n) = (n+1)T(n) = (n+1)2 2 那么，取那么，取n0 = 1 n0 = 1 及及 c=4 c=4

22、時(shí)，時(shí)， T(n) = cnT(n) = cn2 2 成立。成立。 所以，所以，T(n) = O(nT(n) = O(n2 2) ) 大大O O表示法就是取運(yùn)行時(shí)間函數(shù)的主項(xiàng)表示法就是取運(yùn)行時(shí)間函數(shù)的主項(xiàng)數(shù)據(jù)結(jié)構(gòu)引言課件33F(N)的選擇的選擇 大大O O表示法的表示法的O O是單詞是單詞OrderOrder的首字母，表的首字母，表示示“數(shù)量級(jí)數(shù)量級(jí)” 大大O O表示法并不需要給出運(yùn)行時(shí)間的精確表示法并不需要給出運(yùn)行時(shí)間的精確值，而只需要給出一個(gè)數(shù)量級(jí)，表示當(dāng)值，而只需要給出一個(gè)數(shù)量級(jí)，表示當(dāng)問(wèn)題規(guī)模很大時(shí)算法運(yùn)行時(shí)間的增長(zhǎng)是問(wèn)題規(guī)模很大時(shí)算法運(yùn)行時(shí)間的增長(zhǎng)是受限于哪一個(gè)數(shù)量級(jí)的函數(shù)受限于哪一

23、個(gè)數(shù)量級(jí)的函數(shù) 在選擇在選擇F(N)F(N)時(shí)，通常選擇的是比較簡(jiǎn)單時(shí)，通常選擇的是比較簡(jiǎn)單的函數(shù)形式，并忽略低次項(xiàng)和系數(shù)。的函數(shù)形式，并忽略低次項(xiàng)和系數(shù)。 數(shù)據(jù)結(jié)構(gòu)引言課件34典型的增長(zhǎng)率典型的增長(zhǎng)率c c常量常量logNlogN對(duì)數(shù)對(duì)數(shù)LogLog2 2N N對(duì)數(shù)的平方對(duì)數(shù)的平方N N線性線性NlogNNlogNNlogNNlogNN N2 2平方平方N N3 3立方立方2 2N N指數(shù)指數(shù)數(shù)據(jù)結(jié)構(gòu)引言課件35算法按時(shí)間復(fù)雜度分類算法按時(shí)間復(fù)雜度分類 多項(xiàng)式時(shí)間：漸進(jìn)時(shí)間復(fù)雜度有多項(xiàng)式時(shí)多項(xiàng)式時(shí)間：漸進(jìn)時(shí)間復(fù)雜度有多項(xiàng)式時(shí)間限界的算法間限界的算法 指數(shù)時(shí)間算法：漸進(jìn)時(shí)間復(fù)雜度有指數(shù)時(shí)指數(shù)時(shí)

24、間算法：漸進(jìn)時(shí)間復(fù)雜度有指數(shù)時(shí)間限界的算法間限界的算法 多項(xiàng)式時(shí)間復(fù)雜度的關(guān)系：多項(xiàng)式時(shí)間復(fù)雜度的關(guān)系： O(1) O(logN) O(N) O(NlogN)O(1) O(logN) O(N) O(NlogN) O(N O(N2 2) O(N) O(N3 3) ) 指數(shù)時(shí)間復(fù)雜度的關(guān)系：指數(shù)時(shí)間復(fù)雜度的關(guān)系： O(2O(2N N) O(N!) O(N) O(N!) O(NN N) )數(shù)據(jù)結(jié)構(gòu)引言課件36算法分析算法分析時(shí)間復(fù)雜度的概念時(shí)間復(fù)雜度的概念 算法運(yùn)算量的計(jì)算算法運(yùn)算量的計(jì)算漸進(jìn)表示法漸進(jìn)表示法時(shí)間復(fù)雜度的計(jì)算時(shí)間復(fù)雜度的計(jì)算算法的優(yōu)化算法的優(yōu)化空間復(fù)雜度的概念空間復(fù)雜度的概念 數(shù)據(jù)結(jié)

25、構(gòu)引言課件37大大O表示法的計(jì)算表示法的計(jì)算 時(shí)間復(fù)雜度的計(jì)算先定義標(biāo)準(zhǔn)操作，再時(shí)間復(fù)雜度的計(jì)算先定義標(biāo)準(zhǔn)操作，再計(jì)算標(biāo)準(zhǔn)操作的次數(shù)，得到一個(gè)標(biāo)準(zhǔn)操計(jì)算標(biāo)準(zhǔn)操作的次數(shù)，得到一個(gè)標(biāo)準(zhǔn)操作次數(shù)和問(wèn)題規(guī)模的函數(shù)。然后取出函作次數(shù)和問(wèn)題規(guī)模的函數(shù)。然后取出函數(shù)的主項(xiàng)，就是它的時(shí)間復(fù)雜度的大數(shù)的主項(xiàng)，就是它的時(shí)間復(fù)雜度的大O O表表示。示。 簡(jiǎn)化方法：根據(jù)兩個(gè)定理。簡(jiǎn)化方法：根據(jù)兩個(gè)定理。數(shù)據(jù)結(jié)構(gòu)引言課件38大大O表示法的定理表示法的定理求和定理求和定理：假定假定T1(n)T1(n)、T2(n)T2(n)是程序是程序P1P1、P2P2的運(yùn)的運(yùn)行時(shí)間，并且行時(shí)間，并且T1(n)T1(n)是是O(f(n)O

26、(f(n)的，而的，而T2(n)T2(n)是是O(g(n)O(g(n)的。那么，先運(yùn)行的。那么，先運(yùn)行P1P1、再運(yùn)行、再運(yùn)行P2 P2 的總的的總的運(yùn)行時(shí)間是：運(yùn)行時(shí)間是：T1(n)T1(n)T2(n)T2(n)O(MAX(f(n)O(MAX(f(n)，g(n)g(n)。求積定理：如果求積定理：如果T1(n) T1(n) 和和 T2(n)T2(n)分別是分別是O(f(n)O(f(n)和和O(g(n)O(g(n)的，那么的，那么T1(n)T1(n)T2(n)T2(n)是是O(f(n)O(f(n)g(n) g(n) 的。的。數(shù)據(jù)結(jié)構(gòu)引言課件39大大O表示法的計(jì)算規(guī)則表示法的計(jì)算規(guī)則 規(guī)則規(guī)則1

27、1：每個(gè)簡(jiǎn)單語(yǔ)句，如賦值語(yǔ)句、輸入輸：每個(gè)簡(jiǎn)單語(yǔ)句，如賦值語(yǔ)句、輸入輸出語(yǔ)句，它們的運(yùn)行時(shí)間與問(wèn)題規(guī)模無(wú)關(guān)，在出語(yǔ)句，它們的運(yùn)行時(shí)間與問(wèn)題規(guī)模無(wú)關(guān)，在每個(gè)計(jì)算機(jī)系統(tǒng)中運(yùn)行時(shí)間都是一個(gè)常量，因每個(gè)計(jì)算機(jī)系統(tǒng)中運(yùn)行時(shí)間都是一個(gè)常量，因此時(shí)間復(fù)雜度為此時(shí)間復(fù)雜度為 O(1)O(1)。 規(guī)則規(guī)則2 2：條件語(yǔ)句，：條件語(yǔ)句，if if then then else else ，的運(yùn)行時(shí)間為執(zhí)行條件判斷的，的運(yùn)行時(shí)間為執(zhí)行條件判斷的代價(jià)代價(jià) ，一般為，一般為O(1)O(1)，再加上執(zhí)行，再加上執(zhí)行 then then 后面后面的語(yǔ)句的代價(jià)的語(yǔ)句的代價(jià)( (若條件為真若條件為真) )，或執(zhí)行，或執(zhí)行els

28、e else 后后面的語(yǔ)句代價(jià)面的語(yǔ)句代價(jià)( (若條件為假若條件為假) )之和，即之和，即max(O(thenmax(O(then子句子句) )，O(elseO(else子句子句)。數(shù)據(jù)結(jié)構(gòu)引言課件40 規(guī)則規(guī)則3 3：循環(huán)語(yǔ)句的執(zhí)行時(shí)間是循環(huán)控制行和循環(huán)體：循環(huán)語(yǔ)句的執(zhí)行時(shí)間是循環(huán)控制行和循環(huán)體執(zhí)行時(shí)間的總和。循環(huán)控制一般是一個(gè)簡(jiǎn)單的條件執(zhí)行時(shí)間的總和。循環(huán)控制一般是一個(gè)簡(jiǎn)單的條件判斷，因此循環(huán)語(yǔ)句的執(zhí)行時(shí)間是循環(huán)體的運(yùn)行時(shí)判斷，因此循環(huán)語(yǔ)句的執(zhí)行時(shí)間是循環(huán)體的運(yùn)行時(shí)間乘循環(huán)次數(shù)。間乘循環(huán)次數(shù)。 規(guī)則規(guī)則4 4：嵌套循環(huán)語(yǔ)句，對(duì)外層循環(huán)的每個(gè)循環(huán)周期，：嵌套循環(huán)語(yǔ)句，對(duì)外層循環(huán)的每個(gè)循環(huán)周期

29、，內(nèi)存循環(huán)都要執(zhí)行它的所有循環(huán)周期，因此，可用內(nèi)存循環(huán)都要執(zhí)行它的所有循環(huán)周期，因此，可用求積定理計(jì)算整個(gè)循環(huán)的時(shí)間復(fù)雜度，即最內(nèi)層循求積定理計(jì)算整個(gè)循環(huán)的時(shí)間復(fù)雜度，即最內(nèi)層循環(huán)體的運(yùn)行時(shí)間乘所有循環(huán)的循環(huán)次數(shù)。例語(yǔ)句：環(huán)體的運(yùn)行時(shí)間乘所有循環(huán)的循環(huán)次數(shù)。例語(yǔ)句： for (i=0; in; i+) for (i=0; in; i+) for (j=0; jn; j+) k+; for (j=0; jn; j+) k+; 的時(shí)間復(fù)雜性為的時(shí)間復(fù)雜性為O(nO(n2 2) )數(shù)據(jù)結(jié)構(gòu)引言課件41 連續(xù)語(yǔ)句：利用求和定理把這些語(yǔ)句的時(shí)連續(xù)語(yǔ)句：利用求和定理把這些語(yǔ)句的時(shí)間復(fù)雜性相加。例程序段：間

30、復(fù)雜性相加。例程序段： for (i=0; in; i+) ai=0; for (i=0; in; i+) ai=0; for (i=0; in; i+) for (i=0; in; i+) for (j=0; jn; j+) ai= i+j; for (j=0; jn; j+) ai= i+j; 有兩個(gè)連續(xù)的循環(huán)組成。第一個(gè)循環(huán)的時(shí)有兩個(gè)連續(xù)的循環(huán)組成。第一個(gè)循環(huán)的時(shí)間復(fù)雜度為間復(fù)雜度為O O（n n），第二個(gè)循環(huán)的時(shí)間復(fù)），第二個(gè)循環(huán)的時(shí)間復(fù)雜度為雜度為O O（n n2 2）。根據(jù)求和定理，整段程序）。根據(jù)求和定理，整段程序的的時(shí)間復(fù)雜性為的的時(shí)間復(fù)雜性為O(nO(n2 2) )數(shù)據(jù)結(jié)構(gòu)引

31、言課件42大大O的簡(jiǎn)化計(jì)算的簡(jiǎn)化計(jì)算 在程序中找出最復(fù)雜、運(yùn)行時(shí)間最長(zhǎng)的在程序中找出最復(fù)雜、運(yùn)行時(shí)間最長(zhǎng)的程序段，計(jì)算它的時(shí)間復(fù)雜度。也就是程序段，計(jì)算它的時(shí)間復(fù)雜度。也就是整個(gè)程序的時(shí)間復(fù)雜度整個(gè)程序的時(shí)間復(fù)雜度 在在max1max1中，最復(fù)雜的程序段是兩個(gè)循環(huán)，中，最復(fù)雜的程序段是兩個(gè)循環(huán)，這兩個(gè)循環(huán)的時(shí)間復(fù)雜度都是相同的，這兩個(gè)循環(huán)的時(shí)間復(fù)雜度都是相同的，為為O(n)O(n)，因此整個(gè)程序的時(shí)間復(fù)雜度是，因此整個(gè)程序的時(shí)間復(fù)雜度是O(n)O(n)的的 數(shù)據(jù)結(jié)構(gòu)引言課件43算法分析算法分析時(shí)間復(fù)雜度的概念時(shí)間復(fù)雜度的概念 算法運(yùn)算量的計(jì)算算法運(yùn)算量的計(jì)算漸進(jìn)表示法漸進(jìn)表示法時(shí)間復(fù)雜度的計(jì)算

32、時(shí)間復(fù)雜度的計(jì)算算法的優(yōu)化算法的優(yōu)化空間復(fù)雜度的概念空間復(fù)雜度的概念 數(shù)據(jù)結(jié)構(gòu)引言課件44典型實(shí)例典型實(shí)例-最大連續(xù)子序列問(wèn)題最大連續(xù)子序列問(wèn)題 給定給定(可能是負(fù)的可能是負(fù)的)整數(shù)序列整數(shù)序列 ，尋找，尋找(并并標(biāo)識(shí)標(biāo)識(shí)) 的值為最大的序列。如果所有的的值為最大的序列。如果所有的整數(shù)都是負(fù)的，那么最大連續(xù)子序列的和是零。整數(shù)都是負(fù)的，那么最大連續(xù)子序列的和是零。 例如，假設(shè)輸入是例如，假設(shè)輸入是-2, 11, -4, 13, -5, 2，那么答案，那么答案是是20，它表示連續(xù)子序列包含了第，它表示連續(xù)子序列包含了第2項(xiàng)到第項(xiàng)到第4項(xiàng)（如項(xiàng)（如粗體字部分）。又如第二個(gè)例子，對(duì)于輸入粗體字部分）

33、。又如第二個(gè)例子，對(duì)于輸入1, -3, 4, -2, -1, 6，答案是，答案是7，這個(gè)子序列包含最后四項(xiàng)。，這個(gè)子序列包含最后四項(xiàng)。NAAA,.,2112,.,NA AA12,.,NA AAjikkA數(shù)據(jù)結(jié)構(gòu)引言課件45解法一解法一 窮舉法窮舉法 分別求子序列分別求子序列 0，0，0，1，。，。，0，n 1，1，1，2，。，。1，n 。 n，n 的和，求出最大值的和，求出最大值數(shù)據(jù)結(jié)構(gòu)引言課件46int maxSubsequenceSum(int a, int size, int &start, int &end) int maxSum = 0; for (int i = 0; i size

34、; i+ ) for( int j = i; j size; j+ ) int thisSum = 0; for( int k = i; k maxSum ) maxSum = thisSum; start = i; end = j; return maxSum;數(shù)據(jù)結(jié)構(gòu)引言課件47時(shí)間復(fù)雜度分析時(shí)間復(fù)雜度分析 最里層的語(yǔ)句最里層的語(yǔ)句thisSum += a k ;thisSum += a k ;在最里層循環(huán)在最里層循環(huán)中執(zhí)行中執(zhí)行j-i+1j-i+1次。第二個(gè)循環(huán)的規(guī)模是次。第二個(gè)循環(huán)的規(guī)模是n-in-i，最外，最外層的循壞規(guī)模是層的循壞規(guī)模是n n。因此最里層語(yǔ)句執(zhí)行的次數(shù)是。因此最里層

35、語(yǔ)句執(zhí)行的次數(shù)是6232)(1() 1(12310101101nnnininijnininijninijjik 數(shù)據(jù)結(jié)構(gòu)引言課件48方法二方法二 - O(n2)的算法的算法 由于由于 ，因此，方法一中，因此，方法一中最里層的循環(huán)可以省略。最里層的循環(huán)可以省略。1jikkjjikkAAA數(shù)據(jù)結(jié)構(gòu)引言課件49int maxSubsequenceSum(int a, int size, int &start, int &end) int maxSum = 0; for( int i = 0; i size; i+ ) int thisSum = 0; for( int j = i; j maxSum

36、 ) maxSum = thisSum;start = i; end = j; return maxSum; 數(shù)據(jù)結(jié)構(gòu)引言課件50算法三算法三 O(N) 如果一個(gè)子序列的和是負(fù)的，則它不可能是最大如果一個(gè)子序列的和是負(fù)的，則它不可能是最大連續(xù)子序列的一部分，因?yàn)槲覀兛梢酝ㄟ^(guò)不包含連續(xù)子序列的一部分，因?yàn)槲覀兛梢酝ㄟ^(guò)不包含它來(lái)得到一個(gè)更大的連續(xù)子序列。它來(lái)得到一個(gè)更大的連續(xù)子序列。 如：如：-2, 11, -4, 13, -5, 2-2, 11, -4, 13, -5, 2的最大子序列不的最大子序列不可能從可能從-2-2開(kāi)始開(kāi)始 1, -3, 4, -2, -1, 61, -3, 4, -2,

37、-1, 6的最大子序列不可能包的最大子序列不可能包含含11，-3-3數(shù)據(jù)結(jié)構(gòu)引言課件51算法三算法三 O(N) 所有與最大連續(xù)子序列毗鄰的連續(xù)子序列一定有負(fù)的（或所有與最大連續(xù)子序列毗鄰的連續(xù)子序列一定有負(fù)的（或0 0）和（否則會(huì)包含它們）。和（否則會(huì)包含它們）。 在算法二中，當(dāng)檢測(cè)出一個(gè)負(fù)的子序列時(shí)，不但可以從內(nèi)在算法二中，當(dāng)檢測(cè)出一個(gè)負(fù)的子序列時(shí)，不但可以從內(nèi)層循環(huán)中跳出來(lái)，而且還可以讓層循環(huán)中跳出來(lái)，而且還可以讓i i直接增加到直接增加到j(luò)+1j+1。 如：如：1, -3, 4, -2, -1, 61, -3, 4, -2, -1, 6，當(dāng)檢測(cè)序列，當(dāng)檢測(cè)序列11，-3-3后，發(fā)后，發(fā)現(xiàn)

38、是負(fù)值，則表示該子序列不可能包含在最大子序列中。現(xiàn)是負(fù)值，則表示該子序列不可能包含在最大子序列中。因此，接下去就可以從因此，接下去就可以從4 4開(kāi)始檢測(cè)。開(kāi)始檢測(cè)。 注意還有一種情況，當(dāng)檢測(cè)序列注意還有一種情況，當(dāng)檢測(cè)序列11，-3-3后，可以確定他不后，可以確定他不在最大子序列中，但在最大子序列中，但1 1仍可能是最大子序列，如果仍可能是最大子序列，如果-3-3后面都后面都是負(fù)值。因此在找到新的最大子序列前，必須保存是負(fù)值。因此在找到新的最大子序列前，必須保存1 1是最大是最大子序列的事實(shí)。子序列的事實(shí)。數(shù)據(jù)結(jié)構(gòu)引言課件52int maxSubsequenceSum(int a, int s

39、ize, int &start, int &end) int maxSum = 0, thisSum = 0, startTmp = 0; start = end = 0; for( int j = 0; j size ; j+ ) thisSum += aj; if ( thisSum maxSum ) maxSum = thisSum; start = startTmp; end = j; return maxSum; 數(shù)據(jù)結(jié)構(gòu)引言課件53算法分析算法分析時(shí)間復(fù)雜度的概念時(shí)間復(fù)雜度的概念 算法運(yùn)算量的計(jì)算算法運(yùn)算量的計(jì)算漸進(jìn)表示法漸進(jìn)表示法時(shí)間復(fù)雜度的計(jì)算時(shí)間復(fù)雜度的計(jì)算算法的優(yōu)化算法的優(yōu)化空間復(fù)雜度的概念空間復(fù)雜度的概念 數(shù)據(jù)結(jié)構(gòu)引言課件54算法的空間復(fù)雜度算法的空間復(fù)雜度 固定空間需求：與處理的問(wèn)題規(guī)模無(wú)關(guān)固定空間需求：與處理的問(wèn)題規(guī)模無(wú)關(guān) 可變空間需求：與處理的數(shù)據(jù)量有關(guān)可變空間需求