數(shù)據(jù)結(jié)構(gòu)引言課件

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)：思想與實現(xiàn)數(shù)據(jù)結(jié)構(gòu)：思想與實現(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語言版），嚴蔚敏、吳偉民，清華大學(xué)出版社，語言版），嚴蔚敏、吳偉民，清華大學(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著，潘金貴譯，機械工業(yè)出版社，著，潘金貴譯，機械工業(yè)出版社，2006.9算法之道算法之道，鄒恒明，機械工業(yè)出版社，鄒恒明，機械工業(yè)出版社，2012.4數(shù)據(jù)結(jié)構(gòu)引言課件44課程說明 講授內(nèi)容：講授內(nèi)容： 32學(xué)時安排學(xué)時安排.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) 沒有標(biāo)準(zhǔn)

3、的定義，但有共識沒有標(biāo)準(zhǔn)的定義，但有共識 數(shù)據(jù)結(jié)構(gòu)：通過抽象的方法研究一組有特定數(shù)據(jù)結(jié)構(gòu)：通過抽象的方法研究一組有特定關(guān)系的數(shù)據(jù)的存儲與處理關(guān)系的數(shù)據(jù)的存儲與處理 數(shù)據(jù)結(jié)構(gòu)的研究內(nèi)容：數(shù)據(jù)結(jié)構(gòu)的研究內(nèi)容：數(shù)據(jù)之間的邏輯關(guān)系，以及這種關(guān)系對應(yīng)的操作數(shù)據(jù)之間的邏輯關(guān)系，以及這種關(guān)系對應(yīng)的操作如何存儲某種邏輯關(guān)系（存儲實現(xiàn)）如何存儲某種邏輯關(guān)系（存儲實現(xiàn)）在這種存儲模式下，關(guān)系的操作是如何實現(xiàn)的在這種存儲模式下，關(guān)系的操作是如何實現(xiàn)的（運算實現(xiàn)）（運算實現(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)系外沒有的聯(lián)系外沒有其他的關(guān)系。其他的關(guān)系。 線性結(jié)構(gòu)：數(shù)據(jù)元素的有序序列。除了第線性結(jié)構(gòu)：數(shù)據(jù)元素的有序序列。除了第一個和最后一個元素外，其余元素都有一一個和最后一個元素外，其余元素都有一個前趨和一個后繼個前趨和一個后繼 樹形結(jié)構(gòu)：除了根元素外，每個節(jié)點有且樹形結(jié)構(gòu)：除了根元素外，每個節(jié)點有且僅有一個前趨，后繼數(shù)目不限僅有一個前趨，后繼數(shù)目不限 圖型結(jié)構(gòu)：每個元素的前趨和后繼數(shù)目都圖型結(jié)構(gòu)：每個元素的前趨和后繼數(shù)目都不限不限數(shù)據(jù)結(jié)構(gòu)引言課件8集合結(jié)構(gòu)集合結(jié)構(gòu)線性結(jié)構(gòu)線性結(jié)構(gòu)樹形結(jié)構(gòu)樹形結(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)建一個數(shù)

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

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

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

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

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

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

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

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

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

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

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

16、組arrayarray中，中，要求設(shè)計一個算法求數(shù)組中的最大值與要求設(shè)計一個算法求數(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運算量的計算運算量的計算 用乘法、賦值和條件判斷作為標(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找出運算量的函數(shù)找出運算量的函數(shù) 如找出如找出max1max1的最壞情況下的運行時間函數(shù)的最壞情況下的運行時間函數(shù) 第一個第一

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

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

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

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

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

24、間算法：漸進時間復(fù)雜度有指數(shù)時間限界的算法間限界的算法 多項式時間復(fù)雜度的關(guān)系：多項式時間復(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ù)時間復(fù)雜度的關(guān)系：指數(shù)時間復(fù)雜度的關(guān)系： O(2O(2N N) O(N!) O(N) O(N!) O(NN N) )數(shù)據(jù)結(jié)構(gòu)引言課件36算法分析算法分析時間復(fù)雜度的概念時間復(fù)雜度的概念 算法運算量的計算算法運算量的計算漸進表示法漸進表示法時間復(fù)雜度的計算時間復(fù)雜度的計算算法的優(yōu)化算法的優(yōu)化空間復(fù)雜度的概念空間復(fù)雜度的概念 數(shù)據(jù)結(jié)

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

26、(f(n)的，而的，而T2(n)T2(n)是是O(g(n)O(g(n)的。那么，先運行的。那么，先運行P1P1、再運行、再運行P2 P2 的總的的總的運行時間是：運行時間是：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表示法的計算規(guī)則表示法的計算規(guī)則 規(guī)則規(guī)則1

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

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

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

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

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

33、。又如第二個例子，對于輸入1, -3, 4, -2, -1, 6，答案是，答案是7，這個子序列包含最后四項。，這個子序列包含最后四項。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時間復(fù)雜度分析時間復(fù)雜度分析 最里層的語句最里層的語句thisSum += a k ;thisSum += a k ;在最里層循環(huán)在最里層循環(huán)中執(zhí)行中執(zhí)行j-i+1j-i+1次。第二個循環(huán)的規(guī)模是次。第二個循環(huán)的規(guī)模是n-in-i，最外，最外層的循壞規(guī)模是層的循壞規(guī)模是n n。因此最里層語句執(zhí)行的次數(shù)是。因此最里層

35、語句執(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) 如果一個子序列的和是負的，則它不可能是最大如果一個子序列的和是負的，則它不可能是最大連續(xù)子序列的一部分，因為我們可以通過不包含連續(xù)子序列的一部分，因為我們可以通過不包含它來得到一個更大的連續(xù)子序列。它來得到一個更大的連續(xù)子序列。 如：如：-2, 11, -4, 13, -5, 2-2, 11, -4, 13, -5, 2的最大子序列不的最大子序列不可能從可能從-2-2開始開始 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ù)子序列一定有負的（或所有與最大連續(xù)子序列毗鄰的連續(xù)子序列一定有負的（或0 0）和（否則會包含它們）。和（否則會包含它們）。 在算法二中，當(dāng)檢測出一個負的子序列時，不但可以從內(nèi)在算法二中，當(dāng)檢測出一個負的子序列時，不但可以從內(nèi)層循環(huán)中跳出來，而且還可以讓層循環(huán)中跳出來，而且還可以讓i i直接增加到直接增加到j(luò)+1j+1。 如：如：1, -3, 4, -2, -1, 61, -3, 4, -2, -1, 6，當(dāng)檢測序列，當(dāng)檢測序列11，-3-3后，發(fā)后，發(fā)現(xiàn)

38、是負值，則表示該子序列不可能包含在最大子序列中?，F(xiàn)是負值，則表示該子序列不可能包含在最大子序列中。因此，接下去就可以從因此，接下去就可以從4 4開始檢測。開始檢測。 注意還有一種情況，當(dāng)檢測序列注意還有一種情況，當(dāng)檢測序列11，-3-3后，可以確定他不后，可以確定他不在最大子序列中，但在最大子序列中，但1 1仍可能是最大子序列，如果仍可能是最大子序列，如果-3-3后面都后面都是負值。因此在找到新的最大子序列前，必須保存是負值。因此在找到新的最大子序列前，必須保存1 1是最大是最大子序列的事實。子序列的事實。數(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算法分析算法分析時間復(fù)雜度的概念時間復(fù)雜度的概念 算法運算量的計算算法運算量的計算漸進表示法漸進表示法時間復(fù)雜度的計算時間復(fù)雜度的計算算法的優(yōu)化算法的優(yōu)化空間復(fù)雜度的概念空間復(fù)雜度的概念 數(shù)據(jù)結(jié)構(gòu)引言課件54算法的空間復(fù)雜度算法的空間復(fù)雜度 固定空間需求：與處理的問題規(guī)模無關(guān)固定空間需求：與處理的問題規(guī)模無關(guān) 可變空間需求：與處理的數(shù)據(jù)量有關(guān)可變空間需求