數(shù)據(jù)結(jié)構(gòu)單元1引例冒泡排序算法分析和每個(gè)人的學(xué)習(xí)效率、工作效率一樣，算法也有自己的運(yùn)行效率。請(qǐng)分析下面一段算法的時(shí)間復(fù)雜度，它是用冒泡排序法對(duì)數(shù)組a中的n個(gè)整型數(shù)據(jù)進(jìn)行從小到大排序，代碼如圖。引例描述：冒泡排序算法分析素質(zhì)小課堂：學(xué)習(xí)的“新發(fā)展理念”“欲窮千里目，更上一層樓?！痹趶男〉酱蟮呐判蜻^(guò)程中認(rèn)識(shí)到珍惜時(shí)間的同時(shí)，要學(xué)會(huì)把“創(chuàng)新、協(xié)調(diào)、綠色、開(kāi)放、共享”的新發(fā)展理念運(yùn)用到專業(yè)知識(shí)的學(xué)習(xí)中。

分析引例分析與實(shí)現(xiàn)基本操作語(yǔ)句為標(biāo)記（1）處數(shù)據(jù)之間兩兩比較語(yǔ)句以及標(biāo)記（2）-（4）處數(shù)據(jù)兩兩交換語(yǔ)句；外層循環(huán)執(zhí)行n-1次內(nèi)層循環(huán)執(zhí)行n-i次若初始序列a中的數(shù)據(jù)已按關(guān)鍵字排好序，則交換數(shù)據(jù)的次數(shù)為0；反之，若初始序列中的數(shù)據(jù)按逆序排列，則每比較一次就要交換一次，且交換數(shù)據(jù)時(shí)移動(dòng)數(shù)據(jù)的次數(shù)約為3n2/2?？偟臅r(shí)間復(fù)雜度為O(n2)數(shù)據(jù)結(jié)構(gòu)常州信息職業(yè)技術(shù)學(xué)院感謝您的耐心觀看數(shù)據(jù)結(jié)構(gòu)主講人：張靜常州信息職業(yè)技術(shù)學(xué)院1.1數(shù)據(jù)結(jié)構(gòu)的基本概念Part01基本概念和術(shù)語(yǔ)數(shù)據(jù)是信息的載體。數(shù)據(jù)是對(duì)客觀事物的邏輯歸納，是能夠被計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理的數(shù)字、字符以及各種符號(hào)集合的統(tǒng)稱，是計(jì)算機(jī)程序加工的“原料”。姚明的身高為226厘米，是關(guān)于姚明身高的描述數(shù)據(jù)。數(shù)據(jù)（Data）示例基本概念和術(shù)語(yǔ)截止2020年3月31日，全球新冠肺炎確診病例80萬(wàn)例。是全球新冠肺炎確診病例的時(shí)間和人數(shù)數(shù)據(jù)。數(shù)據(jù)元素是組成數(shù)據(jù)的基本單位，也稱為結(jié)點(diǎn)、頂點(diǎn)、記錄等，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。一個(gè)數(shù)據(jù)元素可以是一個(gè)不可分割的原子項(xiàng)，也可以由若干個(gè)數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)元素（DataElement）示例基本概念和術(shù)語(yǔ)圖書(shū)的信息包括：書(shū)號(hào)、書(shū)名、作者、出版社。一本圖書(shū)的信息就是一個(gè)數(shù)據(jù)元素。數(shù)據(jù)項(xiàng)是數(shù)據(jù)元素中具有獨(dú)立含義的最小標(biāo)識(shí)單位，也稱為字段、域、屬性。數(shù)據(jù)項(xiàng)（DataItem）基本概念和術(shù)語(yǔ)姚明的的身高數(shù)據(jù)是一個(gè)不可再分的整型數(shù)據(jù)，這個(gè)整數(shù)既是數(shù)據(jù)元素也是數(shù)據(jù)項(xiàng)；示例一本圖書(shū)數(shù)據(jù)元素由書(shū)號(hào)、書(shū)名、作者、出版社等4個(gè)數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)對(duì)象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。性質(zhì)相同指的是數(shù)據(jù)元素具有相同數(shù)量和類型的數(shù)據(jù)項(xiàng)。數(shù)據(jù)對(duì)象（DataObject）示例基本概念和術(shù)語(yǔ)每本圖書(shū)都有書(shū)號(hào)、書(shū)名、作者、出版社等相同的數(shù)據(jù)項(xiàng)?；靖拍詈托g(shù)語(yǔ)12存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)中的存儲(chǔ)表示或?qū)崿F(xiàn)，也稱為物理結(jié)構(gòu)。數(shù)據(jù)的運(yùn)算初始化、判斷是否為空、存取、遍歷、插入、刪除、更新、查找、排序。邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)是從具體問(wèn)題抽象出來(lái)的數(shù)學(xué)模型，是數(shù)據(jù)元素之間的邏輯關(guān)系。數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)、數(shù)據(jù)的運(yùn)算（操作或算法）。數(shù)據(jù)結(jié)構(gòu)書(shū)號(hào)書(shū)名作者出版社單價(jià)出版日期9787040528121計(jì)算機(jī)應(yīng)用基礎(chǔ)任務(wù)化教程眭碧霞高等教育出版社49.52019.129787040527735信息技術(shù)基礎(chǔ)眭碧霞、張靜高等教育出版社39.52019.109787040487282數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言描述)(第2版)李學(xué)剛高等教育出版社38.12018.039787040509946軟件開(kāi)發(fā)與項(xiàng)目管理（第2版）朱利華高等教育出版社49.52019.019787040496628JavaEE企業(yè)級(jí)項(xiàng)目開(kāi)發(fā)蔣衛(wèi)祥高等教育出版社47.42018.06Part02數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)常被簡(jiǎn)稱為數(shù)據(jù)結(jié)構(gòu)，分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩種，非線性結(jié)構(gòu)主要包括樹(shù)形結(jié)構(gòu)和圖狀結(jié)構(gòu)。邏輯結(jié)構(gòu)線性結(jié)構(gòu)是數(shù)據(jù)元素之間具有線性關(guān)系的數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)元素之間形成一對(duì)一的關(guān)系。它的特征是：除第一個(gè)和最后一個(gè)元素外，每個(gè)數(shù)據(jù)元素有且僅有一個(gè)直接前驅(qū)和一個(gè)直接后繼元素，第一個(gè)元素只有一個(gè)直接后繼元素，最后一個(gè)元素只有一個(gè)直接前驅(qū)元素。數(shù)據(jù)的邏輯結(jié)構(gòu)1.線性結(jié)構(gòu)ABCD非線性結(jié)構(gòu)之一。除了根結(jié)點(diǎn)和葉子結(jié)點(diǎn)之外，樹(shù)中任意一個(gè)結(jié)點(diǎn)只有一個(gè)直接前驅(qū)結(jié)點(diǎn)（父結(jié)點(diǎn)）和多個(gè)直接后繼結(jié)點(diǎn)（孩子結(jié)點(diǎn)），根結(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn)，葉子結(jié)點(diǎn)沒(méi)有后繼結(jié)點(diǎn)。數(shù)據(jù)的邏輯結(jié)構(gòu)2.樹(shù)形結(jié)構(gòu)ABCDEFG根結(jié)點(diǎn)葉子結(jié)點(diǎn)圖狀結(jié)構(gòu)也是非線性結(jié)構(gòu)，數(shù)據(jù)元素之間存在多對(duì)多的關(guān)系，每個(gè)數(shù)據(jù)元素可有多個(gè)前驅(qū)元素和多個(gè)后繼元素。數(shù)據(jù)的邏輯結(jié)構(gòu)3.圖狀結(jié)構(gòu)ABCDEFG集合結(jié)構(gòu)中的數(shù)據(jù)元素除了屬于同一個(gè)集合外，它們之間沒(méi)有其他關(guān)系。各個(gè)數(shù)據(jù)元素是“平等”的，它們的共同關(guān)系就只是屬于同一個(gè)集合。數(shù)據(jù)的邏輯結(jié)構(gòu)4.集合結(jié)構(gòu)Part03數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)主要有兩種：順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。為了加快查找速度，引入了索引（分塊）查找和散列（哈希）查找。因此，從形式上看有4種物理存儲(chǔ)方式，但算法實(shí)現(xiàn)主要采用順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。存儲(chǔ)結(jié)構(gòu)把數(shù)據(jù)元素依次存放在一組地址連續(xù)的存儲(chǔ)單元里，數(shù)據(jù)元素的物理存儲(chǔ)次序和它們的邏輯次序相同，即邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置上相鄰的存儲(chǔ)單元中。通常，使用數(shù)組來(lái)實(shí)現(xiàn)順序存儲(chǔ)結(jié)構(gòu)。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)1.順序存儲(chǔ)結(jié)構(gòu)地址數(shù)據(jù)3000H273004H653008H43300CH893010H103014H3763018H

示例：序列A=(27,65,43,89,10,376)的順序存儲(chǔ)結(jié)構(gòu)把數(shù)據(jù)元素存放在任意的存儲(chǔ)單元里，這組存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的，邏輯上相鄰的數(shù)據(jù)元素在物理位置上不一定相鄰，通常，需要采用指針變量來(lái)記載前驅(qū)和后繼元素的存儲(chǔ)地址。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)2.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)示例：序列A=(27,65,43,89,10,376)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)23索引散列建立附加的索引表來(lái)標(biāo)識(shí)數(shù)據(jù)元素的地址。它不是獨(dú)立的存儲(chǔ)結(jié)構(gòu)，只是為了在查找運(yùn)算時(shí)，能夠減少查找的時(shí)間，提高數(shù)據(jù)查找的性能。3.索引存儲(chǔ)結(jié)構(gòu)根據(jù)結(jié)點(diǎn)的關(guān)鍵字直接計(jì)算出該結(jié)點(diǎn)的存儲(chǔ)地址。它是一種能快速實(shí)現(xiàn)訪問(wèn)的存儲(chǔ)方式，理想情況下，無(wú)需比較即可根據(jù)指定值直接定位記錄的存儲(chǔ)位置。4.散列存儲(chǔ)結(jié)構(gòu)通常情況下，一種數(shù)據(jù)結(jié)構(gòu)既可以用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)，也可用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)，還可以組合使用，具體可根據(jù)實(shí)際問(wèn)題的需要而定。一般來(lái)說(shuō)，若執(zhí)行的主要操作是插入或刪除，最好采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，否則采用順序存儲(chǔ)結(jié)構(gòu)；若預(yù)先可以估計(jì)出元素的個(gè)數(shù)，可采用順序存儲(chǔ)結(jié)構(gòu)，否則宜采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。注意事項(xiàng)數(shù)據(jù)結(jié)構(gòu)常州信息職業(yè)技術(shù)學(xué)院感謝您的耐心觀看數(shù)據(jù)結(jié)構(gòu)主講人：張靜常州信息職業(yè)技術(shù)學(xué)院1.2算法程序=算法+數(shù)據(jù)結(jié)構(gòu)Part01算法及其特性算法（Algorithm）是描述解決特定問(wèn)題的思路、方法和步驟，是求解步驟（指令）的有限序列。輸入：一個(gè)算法應(yīng)該有零個(gè)或多個(gè)輸入。算法的概念算法的重要特性算法及其特性有窮性：一個(gè)算法必須在執(zhí)行有窮步驟之后正常結(jié)束，不能形成無(wú)窮循環(huán)，并且每一個(gè)步驟都在可接受的時(shí)間內(nèi)完成。確定性：算法中的每一條指令必須有確切的含義，不能產(chǎn)生多義性。可行性：算法中的每一條指令必須是切實(shí)可執(zhí)行的。輸出：一個(gè)算法應(yīng)該有一個(gè)或多個(gè)輸出。算法和程序都是用來(lái)表達(dá)解決問(wèn)題的邏輯步驟；算法是對(duì)解決問(wèn)題的方法的具體描述，程序是用某種程序設(shè)計(jì)語(yǔ)言對(duì)算法的具體實(shí)現(xiàn)。算法和程序的關(guān)系區(qū)別算法及其特性程序和算法的最大區(qū)別是程序可以是無(wú)窮的，而算法必須滿足有窮性，即算法不允許無(wú)限循環(huán)。例如，操作系統(tǒng)是個(gè)程序，這個(gè)程序在不遭破壞的情況下永遠(yuǎn)不會(huì)停止，即使沒(méi)有作業(yè)需要處理，它仍處于一個(gè)等待循環(huán)中。Part02算法的描述方法使用類似計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言的所謂偽語(yǔ)言來(lái)描述算法，接近高級(jí)程序設(shè)計(jì)語(yǔ)言的寫(xiě)法，但不一定能直接編譯運(yùn)行的代碼。偽代碼直接以可讀性高的高級(jí)程序設(shè)計(jì)語(yǔ)言來(lái)表示。高級(jí)程序設(shè)計(jì)語(yǔ)言使用中文、英文、數(shù)字等自然語(yǔ)言來(lái)描述算法。自然語(yǔ)言使用流程圖或N-S圖來(lái)描述算法。框圖算法的描述方法本課程采用Java語(yǔ)言表示。Part03算法分析算法設(shè)計(jì)的要求算法分析正確性可讀性健壯性時(shí)間高效性-算法的時(shí)間復(fù)雜度空間高效性-算法的空間復(fù)雜度一個(gè)算法的時(shí)間耗費(fèi)，就是該算法中所有語(yǔ)句的頻度之和。算法分析算法的時(shí)間復(fù)雜度表示算法的時(shí)間效率與算法所處理的數(shù)據(jù)元素個(gè)數(shù)n（問(wèn)題規(guī)模）函數(shù)關(guān)系的最常用函數(shù)是O()函數(shù)（O()讀作大O）。算法的時(shí)間復(fù)雜度T(n)可記作：T(n)=O(f(n))O()說(shuō)明O(1)稱為常數(shù)時(shí)間，表示算法的運(yùn)行時(shí)間是一個(gè)常數(shù)倍，與問(wèn)題規(guī)模無(wú)關(guān)。O(n)稱為線性時(shí)間，執(zhí)行時(shí)間增加的大小與問(wèn)題規(guī)模成線性關(guān)系。O(log2n)稱為冪對(duì)數(shù)時(shí)間，成長(zhǎng)速度比線性時(shí)間慢，比常數(shù)時(shí)間快。O(n2)稱為平方時(shí)間，算法的運(yùn)行時(shí)間成二次方增長(zhǎng)。O(n3)稱為立方時(shí)間，算法的運(yùn)行時(shí)間成三次方增長(zhǎng)。O(2n)稱為指數(shù)時(shí)間，算法的運(yùn)行時(shí)間成2的n次方增長(zhǎng)。O(nlog2n)稱為線性對(duì)數(shù)時(shí)間，介于線性和二次方增長(zhǎng)之間。以上時(shí)間復(fù)雜度的順序：O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)算法分析36示例1示例2示例3示例1假設(shè)某算法運(yùn)行時(shí)間為T(n)=4n3+3n2+9n，求它的時(shí)間復(fù)雜度。例1-1示例4n3+3n2+9n4O(）算法分析37示例1示例2示例3分析下列程序段的時(shí)間復(fù)雜度public

static

voidmain(String[]args){ intn=100,sum=0;//(1)賦初值for(inti=1;i<=n;i++){sum=sum+i;//(2)累加和}System.out.println(sum);}例1-2示例2示例4sum=sum+i;O(n)算法分析38示例1示例2示例3分析下列程序段的時(shí)間復(fù)雜度public

static

voidmain(String[]args){intn=8,count=0;//(1)賦初值

for(inti=1;i<=n;i*=2){ count++;//(2)統(tǒng)計(jì)次數(shù)}System.out.println(count);}例1-3示例3示例4count++O(log2n)示例4算法分析39示例1示例2示例3分析下列程序段的時(shí)間復(fù)雜度public

static

voidmain(String[]args){intn=100,count=0;for(inti=1;i<=n;i++){

for(intj=1;j<=i;j++){ count++;} }System.out.println(count);}例1-4示例4O(n2)

最壞時(shí)間復(fù)雜度：最壞情況下的時(shí)間復(fù)雜度。最壞情況下的時(shí)間復(fù)雜度是算法在任何輸入實(shí)例上運(yùn)