數(shù)據(jù)結(jié)構(gòu).ppt

李云清楊慶紅揭安全 高等學(xué)校精品課程 人民郵電出版社 第2版 數(shù)據(jù)結(jié)構(gòu) datastru 第2版 什么是數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)類型和抽象數(shù)據(jù)類型 算法和算法分析 第一章概述 瑞士著名的計(jì)算機(jī)科學(xué)家NicklausWirth在1976年出版了一本書 書名為 算法 數(shù)據(jù)結(jié)構(gòu) 程序設(shè)計(jì) 它正說明了數(shù)據(jù)結(jié)構(gòu)在程序設(shè)計(jì)中的作用 程序設(shè)計(jì)的實(shí)質(zhì)即為計(jì)算機(jī)處理問題編制一組 指令 首先需要解決兩個問題 即算法和數(shù)據(jù)結(jié)構(gòu) 算法即處理問題的策略 而數(shù)據(jù)結(jié)構(gòu)即為問題的數(shù)學(xué)模型 很多數(shù)值計(jì)算問題的數(shù)學(xué)模型通?？捎靡唤M線性或非線性的代數(shù)方程組或微分方程組來描述 而大量非數(shù)值計(jì)算問題的數(shù)學(xué)模型正是本門課程要討論的數(shù)據(jù)結(jié)構(gòu) 第一章概述 例一 求n個整數(shù)中的最大值 這似乎不成問題 但如果這些整數(shù)的值有可能達(dá)到1012 那么對32位的計(jì)算機(jī)來說 就存在一個如何表示的問題 例二 交叉路口的紅綠燈管理 如今十字路口橫豎兩個方向都有三個紅綠燈 分別控制左拐 直行和右拐 那么如何控制這些紅綠燈既使交通不堵塞 又使流量最大呢 若要編制程序解決問題 首先要解決一個如何表示的問題 例三 煤氣管道的鋪設(shè)問題 如圖需為城市的各小區(qū)之間鋪設(shè)煤氣管道 對n個小區(qū)只需鋪設(shè)n 1條管線 由于地理環(huán)境不同等因素使各條管線所需投資不同 如圖上所標(biāo)識 如何使投資成本最低 這是一個討論圖的生成樹的問題 以上所舉例子中的數(shù)學(xué)模型正是數(shù)據(jù)結(jié)構(gòu)要討論的問題 因此 簡單地說 數(shù)據(jù)結(jié)構(gòu)是一門討論 描述現(xiàn)實(shí)世界實(shí)體的數(shù)學(xué)模型 非數(shù)值計(jì)算 及其上的操作在計(jì)算機(jī)中如何表示和實(shí)現(xiàn) 的學(xué)科 而信息的表示和組織又直接關(guān)系到處理信息的程序的效率 隨著計(jì)算機(jī)的普及 信息量的增加 信息范圍的拓寬 使許多系統(tǒng)程序和應(yīng)用程序的規(guī)模很大 結(jié)構(gòu)又相當(dāng)復(fù)雜 因此 為了編寫出一個 好 的程序 必須分析待處理的對象的特征及各對象之間存在的關(guān)系 這就是數(shù)據(jù)結(jié)構(gòu)這門課所要研究的問題 計(jì)算機(jī)是一門研究用計(jì)算機(jī)進(jìn)行信息表示和處理的科學(xué) 這里面涉及到兩個問題 信息的表示信息的處理 綜上所述 1 1數(shù)據(jù)結(jié)構(gòu) 1 1 1數(shù)據(jù)結(jié)構(gòu) 隨著計(jì)算機(jī)軟 硬件的發(fā)展 計(jì)算機(jī)的應(yīng)用范圍在不斷擴(kuò)大 計(jì)算機(jī)所處理的數(shù)據(jù)的數(shù)量也在不斷擴(kuò)大 計(jì)算機(jī)所處理的數(shù)據(jù)已不再是單純的數(shù)值數(shù)據(jù) 而更多的是非數(shù)值數(shù)據(jù) 需要處理的數(shù)據(jù)并不是雜亂無章的 它們一定有內(nèi)在的聯(lián)系 只有弄清楚它們之間的本質(zhì)的聯(lián)系 才能使用計(jì)算機(jī)對大量的數(shù)據(jù)進(jìn)行有效的處理 例4某電信公司的市話用戶信息表格如下圖所示 這里序號 用戶名 電話號碼等項(xiàng)稱為基本項(xiàng) 它是有獨(dú)立意義的最小標(biāo)識單位 而用戶住址稱為組合項(xiàng) 組合項(xiàng)是由一個或多個基本項(xiàng)或組合項(xiàng)組成 是有獨(dú)立意義的標(biāo)識單位 每一行稱為一個結(jié)點(diǎn) 每一個組合項(xiàng)稱為一個字段 使用計(jì)算機(jī)處理用戶信息表中的數(shù)據(jù)時(shí) 必須弄清楚下面3個問題 1數(shù)據(jù)的邏輯結(jié)構(gòu) 這些數(shù)據(jù)之間有什么樣的內(nèi)在聯(lián)系 除最前和最后兩個結(jié)點(diǎn)之外 表中所有其它的結(jié)點(diǎn)都有且僅有一個和它相鄰位于它之前的一個結(jié)點(diǎn) 也有且僅有一個和它相鄰位于它之后的一個結(jié)點(diǎn) 這些就是用戶信息表的邏輯結(jié)構(gòu) 2數(shù)據(jù)的存儲結(jié)構(gòu) 將用戶信息表中的所有結(jié)點(diǎn)存入計(jì)算機(jī)時(shí) 就必須考慮存儲結(jié)構(gòu) 使用C語言進(jìn)行設(shè)計(jì)時(shí) 常見的方式是用一個結(jié)構(gòu)數(shù)組來存儲整個用戶信息表 每一個數(shù)組元素是一個結(jié)構(gòu) 它對應(yīng)于用戶信息表中的一個結(jié)點(diǎn) 數(shù)據(jù)在計(jì)算機(jī)的存儲方式稱為存儲結(jié)構(gòu) 3數(shù)據(jù)的運(yùn)算集合 數(shù)據(jù)處理必涉及到相關(guān)的運(yùn)算 在上述用戶信息表中 可以有刪除一個用戶 增加一個用戶和查找某個用戶等操作 應(yīng)該明確指明這些操作的含義 比如刪除操作 是刪除序號為5的用戶還是刪除用戶名為王三的用戶是應(yīng)該明確定義的 如果需要可以定義兩個不同的刪除操作 為一批數(shù)據(jù)定義的所有運(yùn)算 或稱操作 構(gòu)成一個運(yùn)算 操作 集合 對待處理的數(shù)據(jù) 只有分析清楚上面3個方面的問題 才能進(jìn)行有效的處理 數(shù)據(jù)結(jié)構(gòu)就是指按一定的邏輯結(jié)構(gòu)組成的一批數(shù)據(jù) 使用某種存儲結(jié)構(gòu)將這批數(shù)據(jù)存儲于計(jì)算機(jī)中 并在這些數(shù)據(jù)上定義了一個運(yùn)算集合 基于這個二維表格 我們可以在上面執(zhí)行的操作有 增加一個元素 刪除元素 查找元素等 存在的問題 線性查找的效率較低 等概率情況下為n 2 數(shù)組存儲時(shí)插入一個元素與刪除一個元素效率較低 解決辦法 改變數(shù)據(jù)存儲結(jié)構(gòu) 在新的存儲結(jié)構(gòu)上開發(fā)新的算法 找95 找35 例5 旅游交通網(wǎng)絡(luò)圖 實(shí)際問題 如何選擇任意兩個城市之間的最短路徑 建立通信網(wǎng)絡(luò)時(shí) 如何在n個城市之間找到n 1連線 使得這n 1條連線的和最小 即花費(fèi)最小的代價(jià)連通各個城市 解決辦法 將城市與城市之間的距離等數(shù)據(jù)在計(jì)算機(jī)中采用圖型結(jié)構(gòu)組織 點(diǎn)與點(diǎn)之間存在多對多的關(guān)系 上述問題便可轉(zhuǎn)化為圖中兩點(diǎn)之間的最短距離和圖的最小生成樹問題 1 1 2數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu)是數(shù)據(jù)和數(shù)據(jù)之間所存在的邏輯關(guān)系 它可以用一個二元組B K R 來表示 其中K是數(shù)據(jù) 即結(jié)點(diǎn)的有限集合 R是集合K上關(guān)系的有限集合 這里的關(guān)系是從集合K到集合K的關(guān)系 這里一般只涉及到一個關(guān)系的邏輯結(jié)構(gòu) 1 1 2數(shù)據(jù)的邏輯結(jié)構(gòu) 例如 有5個人 分別記為a b c d e 其中a是b的父親 b是c的父親 c是d的父親 d是e的父親 如果只討論他們之間所存在的父子關(guān)系 則可以用下面的二元組形式化地予以表達(dá) B K R 其中 K a b c d e R r r 邏輯結(jié)構(gòu)的圖形表示方式 對K中的每個結(jié)點(diǎn)ki用一個方框表示 而結(jié)點(diǎn)之間的關(guān)系用帶箭頭的線段表示 這5人之間的邏輯結(jié)構(gòu)用圖形的方式表達(dá)如下圖所示 若ki K kj R r 則稱ki是kj的相對于關(guān)系r的前驅(qū)結(jié)點(diǎn) kj是ki的相對于關(guān)系r的后繼結(jié)點(diǎn) 因?yàn)橐话阒挥懻摼哂幸环N關(guān)系的邏輯結(jié)構(gòu) 即R r 所以簡稱ki是kj前驅(qū) kj是ki的后繼 如果某個結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn) 稱之為開始結(jié)點(diǎn) 如果某個結(jié)點(diǎn)沒有后繼結(jié)點(diǎn) 稱之為終端結(jié)點(diǎn) 既不是開始結(jié)點(diǎn)也不是終端結(jié)點(diǎn)的結(jié)點(diǎn)稱為內(nèi)部結(jié)點(diǎn) 線性邏輯結(jié)構(gòu) 二 樹型結(jié)構(gòu)結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對多的關(guān)系 三 圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多對多的關(guān)系 1 1 3數(shù)據(jù)的存儲結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu)是獨(dú)立于計(jì)算機(jī)的 它與數(shù)據(jù)在計(jì)算機(jī)中的存儲無關(guān) 要對數(shù)據(jù)進(jìn)行處理 就必須將數(shù)據(jù)存儲在計(jì)算機(jī)中 如果將數(shù)據(jù)在計(jì)算機(jī)中無規(guī)律地存儲 那么在處理時(shí)是非常糟的 是沒有用的 試想一下 如果一本英漢字典中的單詞是隨意編排的 這本字典誰會用 對于一個數(shù)據(jù)結(jié)構(gòu)B K R 必須建立從結(jié)點(diǎn)集合到計(jì)算機(jī)某個存儲區(qū)域M的一個映象 這個映象要直接或間接地表達(dá)結(jié)點(diǎn)之間的關(guān)系R 數(shù)據(jù)在計(jì)算機(jī)中的存儲方式稱為數(shù)據(jù)的存儲結(jié)構(gòu) 數(shù)據(jù)的存儲結(jié)構(gòu)主要有4種 數(shù)據(jù)的存儲結(jié)構(gòu)主要有4種 1順序存儲順序存儲通常用于存儲具有線性結(jié)構(gòu)的數(shù)據(jù) 將邏輯上相鄰的結(jié)點(diǎn)存儲在連續(xù)存儲區(qū)域M的相鄰的存儲單元中 使得邏輯相鄰的結(jié)點(diǎn)一定是物理位置相鄰 對于一個數(shù)據(jù)結(jié)構(gòu)B K R 其中K k1 k2 k3 k4 k5 k6 k7 k8 k9 R r r 它的順序存儲方式如圖所示 存儲地址M 100110021003100410051006100710081009 特點(diǎn) 用物理相鄰的位置關(guān)系表示其邏輯關(guān)系 2鏈?zhǔn)酱鎯︽準(zhǔn)酱鎯Ψ绞绞墙o每個結(jié)點(diǎn)附加一個指針段 一個結(jié)點(diǎn)的指針?biāo)傅氖窃摻Y(jié)點(diǎn)的后繼的存儲地址 因?yàn)橐粋€結(jié)點(diǎn)可能有多個后繼 所以指針段可以是一個指針 也可以是一個多個指針 例 數(shù)據(jù)的邏輯結(jié)構(gòu)B K R 其中K k1 k2 k3 k4 k5 R r r 這是一個線性結(jié)構(gòu) 它的鏈?zhǔn)酱鎯θ鐖D所示 100010011002100310041005100610071008 存儲地址infonext 特點(diǎn) 邏輯上相鄰物理上不一定相鄰 3索引存儲在線性結(jié)構(gòu)中 設(shè)開始結(jié)點(diǎn)的索引號為1 其它結(jié)點(diǎn)的索引號等于其前繼結(jié)點(diǎn)的索引號加1 則每一個結(jié)點(diǎn)都有唯一的索引號 索引號就是根據(jù)結(jié)點(diǎn)的索引號確定該結(jié)點(diǎn)的存儲地址 4散列存儲散列存儲的思想是構(gòu)造一個從集合K到存儲區(qū)域M的一個函數(shù)h 該函數(shù)的定義域?yàn)镵 值域?yàn)镸 K中的每個結(jié)點(diǎn)ki在計(jì)算機(jī)中的存儲地址由h ki 確定 1 1 4數(shù)據(jù)的運(yùn)算集合 對于一批數(shù)據(jù) 數(shù)據(jù)的運(yùn)算是定義在數(shù)據(jù)的邏輯結(jié)構(gòu)之上的 而運(yùn)算的具體實(shí)現(xiàn)就依賴于數(shù)據(jù)的存儲結(jié)構(gòu) 數(shù)據(jù)的運(yùn)算集合要視情況而定 一般而言 數(shù)據(jù)的運(yùn)算包括插入 刪除 檢索 輸出 排序等 插入 在一個結(jié)構(gòu)中增加一個新的結(jié)點(diǎn) 刪除 在一個結(jié)構(gòu)刪除一個結(jié)點(diǎn) 檢索 在一個結(jié)構(gòu)中查找滿足條件的結(jié)點(diǎn) 輸出 將一個結(jié)構(gòu)中所有結(jié)點(diǎn)的值打印 輸出 排序 將一個結(jié)構(gòu)中所有結(jié)點(diǎn)按某種順序重新排列 在程序設(shè)計(jì)中 數(shù)據(jù)和運(yùn)算是兩個不可缺少的因素 所有的程序設(shè)計(jì)活動都是圍繞著數(shù)據(jù)和其上的相關(guān)運(yùn)算而進(jìn)行的 從機(jī)器指令 匯編語言中的數(shù)據(jù)沒有類型的概念 到現(xiàn)在的面向?qū)ο蟪绦蛟O(shè)計(jì)語言中抽象數(shù)據(jù)類型概念的出現(xiàn) 程序設(shè)計(jì)中的數(shù)據(jù)經(jīng)歷了一次次抽象 數(shù)據(jù)的抽象經(jīng)歷了三個發(fā)展階段 1 2數(shù)據(jù)類型和抽象數(shù)據(jù)類型 從無類型的二進(jìn)制數(shù)到基本數(shù)據(jù)類型的產(chǎn)生 從基本數(shù)據(jù)類型到用戶自定義類型的產(chǎn)生 從用戶自定義類型到抽象數(shù)據(jù)類型的出現(xiàn) 1 2 1數(shù)據(jù)類型 數(shù)據(jù)類型 或簡稱類型 反映了數(shù)據(jù)的取值范圍以及對這類數(shù)據(jù)可以施加的運(yùn)算 1 2 2數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)科學(xué)中廣泛使用的一個術(shù)語 在計(jì)算機(jī)科學(xué)中具有非常重要的作用 數(shù)據(jù)結(jié)構(gòu)包括三個方面的內(nèi)容 一組數(shù)據(jù)中各數(shù)據(jù)之間的邏輯關(guān)系 這組數(shù)據(jù)在計(jì)算機(jī)中的存儲方式 對這組數(shù)據(jù)所能施加的運(yùn)算的集合 數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)存在的形式 所有的數(shù)據(jù)都是按照數(shù)據(jù)結(jié)構(gòu)進(jìn)行分類的 簡單數(shù)據(jù)類型對應(yīng)于簡單的數(shù)據(jù)結(jié)構(gòu) 構(gòu)造數(shù)據(jù)類型對應(yīng)于復(fù)雜的數(shù)據(jù)結(jié)構(gòu) 1 2 3抽象數(shù)據(jù)類型 抽象數(shù)據(jù)類型是與表示無關(guān)的數(shù)據(jù)類型 是一個數(shù)據(jù)模型及定義在該模型上的一組運(yùn)算 對一個抽象數(shù)據(jù)類型進(jìn)行定義時(shí) 必須給出它的名字及各運(yùn)算的運(yùn)算符名 即函數(shù)名 并且規(guī)定這些函數(shù)的參數(shù)性質(zhì) 1 2 4抽象數(shù)據(jù)類型的描述和實(shí)現(xiàn) 抽象數(shù)據(jù)類型的描述包括給出抽象數(shù)據(jù)類型的名稱 數(shù)據(jù)的集合 數(shù)據(jù)之間的關(guān)系和操作的集合等方面的描述 抽象數(shù)據(jù)類型的設(shè)計(jì)者根據(jù)這些描述給出操作的具體實(shí)現(xiàn) 抽象數(shù)據(jù)類型的使用者依據(jù)這些描述使用抽象數(shù)據(jù)類型 抽象數(shù)據(jù)類型描述的一般形式如下 ADT抽象數(shù)據(jù)類型名稱 數(shù)據(jù)對象 數(shù)據(jù)關(guān)系 操作集合 操作名1 操作名n ADT抽象數(shù)據(jù)類型名稱 1 3算法和算法分析 1 3 1算法 為了求解某問題 必須給出一系列的運(yùn)算規(guī)則 這一系列的運(yùn)算規(guī)則是有限的 表達(dá)了求解問題方法和步驟 這就是一個算法 一個算法可以用自然語言描述 也可以用高級程序設(shè)計(jì)語言描述 也可以用偽代碼描述 本書采用C語言對算法進(jìn)行描述 算法具有五個基本特征 有窮性 算法的執(zhí)行必須在有限步內(nèi)結(jié)束 確定性 算法的每一步驟必須是確定無二義性的 輸入 算法可以有0個或多個輸入 輸出 算法一定有輸出結(jié)果 可行性 算法中的運(yùn)算都必須是可以實(shí)現(xiàn)的 算法具有有窮性 程序不需要具備有窮性 一般的程序都會在有限時(shí)間內(nèi)終止 但有的程序卻可以不在有限時(shí)間內(nèi)終止 如一個操作系統(tǒng)在正常情況下是永遠(yuǎn)都不會終止的 1 3 2算法的時(shí)間和空間復(fù)雜性 一個算法的優(yōu)劣主要從算法的執(zhí)行時(shí)間和所需要占用的存儲空間兩個方面衡量 算法執(zhí)行時(shí)間的度量不是采用算法執(zhí)行的絕對時(shí)間來計(jì)算的 因?yàn)橐粋€算法在不同的機(jī)器上執(zhí)行所花的時(shí)間不一樣 在不同時(shí)刻也會由于計(jì)算機(jī)資源占用情況的不同 使得算法在同一臺計(jì)算機(jī)上執(zhí)行的時(shí)間也不一樣 所以對于算法的時(shí)間復(fù)雜性 采用算法執(zhí)行過程中其基本操作的執(zhí)行次數(shù) 稱為計(jì)算量來度量 算法中基本操作的執(zhí)行次數(shù)一般是與問題規(guī)模有關(guān)的 對于結(jié)點(diǎn)個數(shù)為n的數(shù)據(jù)處理問題 用T n 表示算法基本操作的執(zhí)行次數(shù) 評價(jià)一個算法的一般作法 1 合理地選擇一個或幾個操作作為 標(biāo)準(zhǔn)操作 2 計(jì)算量 給定輸入下執(zhí)行標(biāo)準(zhǔn)操作的次數(shù) 事實(shí) 一個算法的計(jì)算量通常依賴于問題的規(guī)模 為了便于討論 我們把問題規(guī)模假定為n 則算法在問題規(guī)模 Size 為n的輸入下的計(jì)算量為T n 定義 設(shè)f n 與g n 是定義在正整數(shù)集合上的兩個函數(shù) 如果存在兩個正常數(shù)c和n0 對于所有的n n0 有 f n c g n 則記作f n O g n 也就是說對幾乎所有的n值 函數(shù)f n 以函數(shù)g n 為上界 漸近記號 一 f n O g n 表明 當(dāng)n 時(shí) f n 趨于無窮大的階不大于 即小于等于 g n 趨于無窮大的階 例1 證明n2 2 3為O n2 漸近記號 二 大 記號 定義 f n g n 意味著存在正常數(shù)C和n0 使得當(dāng)n n0 均有0 Cg n f n 成立 f n g n 表明 當(dāng)n 時(shí) f n 趨于無窮大的階不小于g n 趨于無窮大的階 漸近記號 三 大 記號 定義 f n g n 意味著存在正常數(shù)C1 C2和n0使得當(dāng)n n0 均有0 C1g n f n C2g n 成立 f n g n 表明 當(dāng)n 時(shí) f n 和g n 趨于無窮大的階是相同的 例2 求兩個n階方陣的乘積C A Bfor i 0 i n i for j 0 j n j c i j 0 for k 0 k n k c i j a i k b k j n 1 n n 1 n2 n2 n 1 n3 一般情況下 算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù) 當(dāng)n趨向無窮大時(shí) 我們把時(shí)間復(fù)雜度T n O f n 的數(shù)量級 階 稱為算法的漸近時(shí)間復(fù)雜度 上述n階矩陣相乘算法的時(shí)間復(fù)雜度T 為算法中所有語句的頻度之和 T n 2n3 3n2 2n 1按照O記法 當(dāng)n趨向無窮大時(shí)有 limT n n3 lim 2n3 3n2 2n 1 n3 2這表明 當(dāng)n充分大時(shí) T n 和n3之比是一個不等于0的常數(shù) 即T n 和n3是同階的 所以 T n O n3 頻度 是指該語句重復(fù)執(zhí)行的次數(shù) n n 例3 x s 0 將x自增看成是基本操作 則語句頻度為 即時(shí)間復(fù)雜度為 1 如果將s 0也看成是基本操作 則語句頻度為 其時(shí)間復(fù)雜度仍為 1 即常量階 例4 for i 1 i n i x s x 語句頻度為 2n其時(shí)間復(fù)雜度為 O n 即時(shí)間復(fù)雜度為線性階 例5 for i 1 i n i for j 1 j n j x s x 語句頻度為 2n2其時(shí)間復(fù)雜度為 O n2 即時(shí)間復(fù)雜度為平方階 定理 若A n amnm am 1nm 1 a1n a0是一個m次多項(xiàng)式 則A n O nm 證略 例6for i 2 i n i for j 2 j i 1 j x a i j x 語句頻度為 1 2 3 n 2 1 n 2 n 2 2 n 1 n 2 2 n2 3n 2 時(shí)間復(fù)雜度為O n2 即此算法的時(shí)間復(fù)雜度為平方階 一個算法時(shí)間為O 1 的算法 它的基本運(yùn)算執(zhí)行的次數(shù)是固定的 因此 總的時(shí)間由一個常數(shù) 即零次多項(xiàng)式 來限界 而一個時(shí)間為O n2 的算法則由一個二次多項(xiàng)式來限界 以下六種計(jì)算算法時(shí)間的多項(xiàng)式是最常用的 其關(guān)系為 O 1 O logn O n O nlogn O n2 O n3 指數(shù)時(shí)間的關(guān)系為 O 2n O n O nn 當(dāng)n取得很大時(shí) 指數(shù)時(shí)間算法和多項(xiàng)式時(shí)間算法在所需時(shí)間上非常懸殊 因此 只要有人能將現(xiàn)有指數(shù)時(shí)間算法中的任何一個算法化簡為多項(xiàng)式時(shí)間算法 那就取得了一個偉大的成就 下面的表格給出了一些具體函數(shù)的O 的表示 如圖所示 有的情況下 算法中基本操作重復(fù)執(zhí)行的次數(shù)還隨問題的輸入數(shù)據(jù)集不同而不同 例如 voidbubble sort inta intn for i n 1 change 1 i 1 最好情況 0次 原有數(shù)據(jù)有序時(shí) 最壞情況 1 2 3 n 1 n n 1 2平均時(shí)間復(fù)雜度為 O n2 算法的時(shí)間復(fù)雜性不僅和問題的規(guī)模大小有關(guān) 還與問題數(shù)據(jù)的初始狀態(tài)有關(guān) 這樣就有了算法在最好 最壞以及在平均狀態(tài)下的時(shí)間復(fù)雜性的概念 算法在最好情況下的時(shí)間復(fù)雜性是指算法計(jì)算量的最小值 算法在最壞情況下的時(shí)間復(fù)雜性是指算法計(jì)算量的最大值 算法的平均情況下的時(shí)間復(fù)雜性是指算法在所有可能的情況下的計(jì)算量經(jīng)過加權(quán)計(jì)算出的平均值 算法的存儲空間需求空間復(fù)雜度 算法所需存儲空間的度量 記作 S n O f n 其中n為問題的規(guī)模 或大小 空間復(fù)雜度 Spacecomp