第1章緒論 數(shù)據(jù)結(jié)構(gòu)與算法Java版

1、第一章第一章 緒論緒論 第一章第一章 緒緒 論論 1.2 基本概念與術(shù)語基本概念與術(shù)語 1.3 算法與算法分析算法與算法分析 1.4 Java提供的泛型方法提供的泛型方法 1.1 數(shù)據(jù)結(jié)構(gòu)課程討論的內(nèi)容數(shù)據(jù)結(jié)構(gòu)課程討論的內(nèi)容 第一章第一章 緒緒 論論 重點(diǎn)：重點(diǎn)： u數(shù)據(jù)結(jié)構(gòu)的基本概念及有關(guān)術(shù)語數(shù)據(jù)結(jié)構(gòu)的基本概念及有關(guān)術(shù)語 u算法及算法的分析方法算法及算法的分析方法 難點(diǎn)：難點(diǎn)： u時間復(fù)雜度的估算時間復(fù)雜度的估算 第一章第一章 緒緒 論論 課前思考課前思考 你過去是否聽說過你過去是否聽說過“數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)”？ 你知道數(shù)據(jù)結(jié)構(gòu)是一門討論什么內(nèi)你知道數(shù)據(jù)結(jié)構(gòu)是一門討論什么內(nèi) 容的學(xué)科嗎？容的學(xué)

2、科嗎？ 1.1 數(shù)據(jù)結(jié)構(gòu)課程討論的內(nèi)容數(shù)據(jù)結(jié)構(gòu)課程討論的內(nèi)容 Niklaus Wirth： （著名的瑞士科學(xué)家沃思教授） Algorithm + Data Structures = Programs ( 算算 法法 + 數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu) = 程程 序序 ） 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu): 算算 法法: 程程 序序: : 為計算機(jī)處理問題而編 制的一組指令集 處理問題的策略 （是對數(shù)據(jù)運(yùn)算的描述，是程序的邏輯抽象） 問題的數(shù)學(xué)模型，它反 映數(shù)據(jù)及其之間關(guān)系。 （存儲結(jié)構(gòu)和邏輯結(jié)構(gòu)） 1.1 數(shù)據(jù)結(jié)構(gòu)課程討論的內(nèi)容數(shù)據(jù)結(jié)構(gòu)課程討論的內(nèi)容 問題求解的主要步驟：問題求解的主要步驟： 1. 1.確定求解問題的

3、確定求解問題的數(shù)學(xué)模型數(shù)學(xué)模型； 2. 2.確定確定存儲結(jié)構(gòu)存儲結(jié)構(gòu)； 3. 3.設(shè)計設(shè)計算法算法； 4. 4.編程編程并測試結(jié)果。并測試結(jié)果。 1.1 數(shù)據(jù)結(jié)構(gòu)課程討論的內(nèi)容數(shù)據(jù)結(jié)構(gòu)課程討論的內(nèi)容 程序設(shè)計的實質(zhì)程序設(shè)計的實質(zhì)是在于解決兩是在于解決兩 個主要問題：個主要問題：一是一是根據(jù)實際問題選根據(jù)實際問題選 擇一種好的數(shù)據(jù)結(jié)構(gòu)；擇一種好的數(shù)據(jù)結(jié)構(gòu)；二是二是設(shè)計一設(shè)計一 個好的算法，而好的算法在很大程個好的算法，而好的算法在很大程 度上取決于描述實際問題的數(shù)據(jù)結(jié)度上取決于描述實際問題的數(shù)據(jù)結(jié) 構(gòu)。構(gòu)。 1.1 數(shù)據(jù)結(jié)構(gòu)課程討論的內(nèi)容數(shù)據(jù)結(jié)構(gòu)課程討論的內(nèi)容 【例例1 1】N個數(shù)的選擇問題個數(shù)

4、的選擇問題 算法：算法：? ? 模型：模型：? ? 如何選擇？如何選擇？ N個數(shù)在計算機(jī)中的組織個數(shù)在計算機(jī)中的組織 1.1 數(shù)據(jù)結(jié)構(gòu)課程討論的內(nèi)容數(shù)據(jù)結(jié)構(gòu)課程討論的內(nèi)容 【例例2 2】生產(chǎn)訂單的自動查詢問題生產(chǎn)訂單的自動查詢問題 算法：算法：? ? 模型：模型：? ? 如何查詢？如何查詢？ 生產(chǎn)訂單數(shù)據(jù)在計算機(jī)生產(chǎn)訂單數(shù)據(jù)在計算機(jī) 中的組織中的組織 1.1 數(shù)據(jù)結(jié)構(gòu)課程討論的內(nèi)容數(shù)據(jù)結(jié)構(gòu)課程討論的內(nèi)容 【例例3 3】城市網(wǎng)絡(luò)的鋪設(shè)問題城市網(wǎng)絡(luò)的鋪設(shè)問題 算法：算法：? ? 模型：模型：? ? 如何為城市的各小區(qū)之如何為城市的各小區(qū)之 間鋪設(shè)網(wǎng)絡(luò)線路間鋪設(shè)網(wǎng)絡(luò)線路,使投資使投資 最小最小?(對

5、對 n 個小區(qū)只需鋪個小區(qū)只需鋪 設(shè)設(shè) n-1 條線路條線路) 圖的最小生成樹圖的最小生成樹 1.1 數(shù)據(jù)結(jié)構(gòu)課程討論的內(nèi)容數(shù)據(jù)結(jié)構(gòu)課程討論的內(nèi)容 方面 過程 數(shù)據(jù)表示數(shù)據(jù)處理 抽象邏輯結(jié)構(gòu)基本運(yùn)算 實現(xiàn)存儲結(jié)構(gòu)算法 評價 不同數(shù)據(jù)結(jié)構(gòu)的比較和算 法性能分析 數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容體系數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容體系: : 簡單地說簡單地說, , 本課程研究的內(nèi)容包括以下三方面：本課程研究的內(nèi)容包括以下三方面： 1. 1. 數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu) 2. 2. 數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)/ /物理結(jié)構(gòu)物理結(jié)構(gòu) 3. 3. 數(shù)據(jù)的運(yùn)算數(shù)據(jù)的運(yùn)算 1.2 基本概念與術(shù)語基本概念與術(shù)語 l數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)

6、與數(shù)據(jù)結(jié)構(gòu) l數(shù)據(jù)類型數(shù)據(jù)類型 l抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型 1.2 基本概念與術(shù)語基本概念與術(shù)語 所有能所有能被輸入被輸入到計算機(jī)中，且能被計算到計算機(jī)中，且能被計算 機(jī)機(jī)處理處理的的符號的總稱符號的總稱。如：實數(shù)、整數(shù)、。如：實數(shù)、整數(shù)、 字符（串）、圖形和聲音等。字符（串）、圖形和聲音等。 數(shù)據(jù)數(shù)據(jù)(Data):(Data): 是是計算機(jī)操作對象計算機(jī)操作對象的集合。的集合。 是計算機(jī)處理的是計算機(jī)處理的信息的信息的某種特定的符某種特定的符 號號表示形式表示形式。 1.2 基本概念與術(shù)語基本概念與術(shù)語 是數(shù)據(jù)（集合）中的一個是數(shù)據(jù)（集合）中的一個“個體個體” 數(shù)據(jù)元素（數(shù)據(jù)元素（Data

7、Element):Data Element): 是數(shù)據(jù)結(jié)構(gòu)中討論的是數(shù)據(jù)結(jié)構(gòu)中討論的基本單位基本單位 不同場合也叫不同場合也叫結(jié)點(diǎn)、頂點(diǎn)、記錄結(jié)點(diǎn)、頂點(diǎn)、記錄 1.2 基本概念與術(shù)語基本概念與術(shù)語 數(shù)據(jù)項（數(shù)據(jù)項（Data ItemData Item） ： 是數(shù)據(jù)結(jié)構(gòu)中討論的是數(shù)據(jù)結(jié)構(gòu)中討論的最小最小單位單位 數(shù)據(jù)元素是由若干個數(shù)據(jù)項組成數(shù)據(jù)元素是由若干個數(shù)據(jù)項組成 例如：例如： 描述一個運(yùn)動員的數(shù)據(jù)元素描述一個運(yùn)動員的數(shù)據(jù)元素 稱之為稱之為組合項組合項, ,其它為其它為簡單項簡單項 年月日 姓名 俱樂部名稱 出生日期 參加日期 職務(wù)業(yè)績 1.2 基本概念與術(shù)語基本概念與術(shù)語 數(shù)據(jù)對象（數(shù)據(jù)對

8、象（Data ObjectData Object） ： 是性質(zhì)相同的數(shù)據(jù)元素的集合是性質(zhì)相同的數(shù)據(jù)元素的集合 例如：例如：學(xué)生成績表是一個數(shù)據(jù)對象學(xué)生成績表是一個數(shù)據(jù)對象 學(xué)號姓名數(shù)學(xué)分析 普通物理高等代數(shù) 20001 20002 20003 20004 20005 張三 李四 丁一 馬二 王五 90 80 67 98 56 56 87 67 90 87 89 67 87 67 68 數(shù)據(jù)對象中的數(shù)據(jù)元素數(shù)據(jù)對象中的數(shù)據(jù)元素不會是孤立的不會是孤立的， 而是彼此相關(guān)的而是彼此相關(guān)的，這種彼此之間的關(guān)系稱為，這種彼此之間的關(guān)系稱為 “結(jié)構(gòu)結(jié)構(gòu)”, ,如書中表如書中表1.11.1、圖圖1.2(a)1

9、.2(a)、圖、圖 1.3 1.3 都形成了其特定的結(jié)構(gòu)。都形成了其特定的結(jié)構(gòu)。 1.2 基本概念與術(shù)語基本概念與術(shù)語 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（Data StructureData Structure） ： 邏輯結(jié)構(gòu)邏輯結(jié)構(gòu) 存儲結(jié)構(gòu)存儲結(jié)構(gòu) 數(shù)據(jù)操作數(shù)據(jù)操作 線性線性結(jié)構(gòu)結(jié)構(gòu) (1:1(1:1的關(guān)系的關(guān)系) ) 樹形樹形結(jié)構(gòu)結(jié)構(gòu) (1:n(1:n的關(guān)系的關(guān)系) ) 圖狀圖狀結(jié)構(gòu)結(jié)構(gòu) (m:n(m:n的關(guān)系的關(guān)系) ) 集合集合結(jié)構(gòu)結(jié)構(gòu) ( (松散關(guān)系松散關(guān)系) ) 順序順序存儲存儲 鏈?zhǔn)芥準(zhǔn)酱鎯Υ鎯?索引索引存儲存儲 散列散列存儲存儲 非線性結(jié)構(gòu)非線性結(jié)構(gòu) 是相互之間存在一種或多種關(guān)系的數(shù)據(jù)元素

10、的集是相互之間存在一種或多種關(guān)系的數(shù)據(jù)元素的集 合合 : :創(chuàng)建、銷毀、插入、刪除、修改等創(chuàng)建、銷毀、插入、刪除、修改等 1.2 基本概念與術(shù)語基本概念與術(shù)語 邏輯結(jié)構(gòu)可用二元組形式定義為邏輯結(jié)構(gòu)可用二元組形式定義為: : Data_Structures = (D, R) 其中其中: : D 是數(shù)據(jù)元素的有限集，是數(shù)據(jù)元素的有限集， R是是 D上關(guān)系的有限集。上關(guān)系的有限集。 也可用數(shù)據(jù)的也可用數(shù)據(jù)的邏輯結(jié)構(gòu)圖邏輯結(jié)構(gòu)圖來形象表示之。來形象表示之。 1.2 基本概念與術(shù)語基本概念與術(shù)語 【例例1 1】設(shè)有數(shù)據(jù)結(jié)構(gòu)為：設(shè)有數(shù)據(jù)結(jié)構(gòu)為： B=（D，R），其中：），其中： D=k1,k2,k3,.k

11、9 R=, , 畫出其邏輯結(jié)構(gòu)的圖示，并確定相對于關(guān)系畫出其邏輯結(jié)構(gòu)的圖示，并確定相對于關(guān)系R，哪些，哪些 結(jié)點(diǎn)是開始結(jié)點(diǎn)，哪些是終端結(jié)點(diǎn)？結(jié)點(diǎn)是開始結(jié)點(diǎn)，哪些是終端結(jié)點(diǎn)？ k2 k1 k4 k5 k3 k8 k6 k9 k7 開始結(jié)點(diǎn)為開始結(jié)點(diǎn)為k1,k2(無前驅(qū)的結(jié)點(diǎn)）無前驅(qū)的結(jié)點(diǎn)） 終端結(jié)點(diǎn)為終端結(jié)點(diǎn)為k6,k7(無后繼的結(jié)點(diǎn)）無后繼的結(jié)點(diǎn)） 1.2 基本概念與術(shù)語基本概念與術(shù)語 【例例2 2】矩陣矩陣 中中9 9個元素之間存在個元素之間存在 兩種關(guān)系，一種是行關(guān)系，一種是列關(guān)系，兩種關(guān)系，一種是行關(guān)系，一種是列關(guān)系，試試 給出其邏輯結(jié)構(gòu)的二元組表示形式。給出其邏輯結(jié)構(gòu)的二元組表示形式。

12、 987 654 321 aaa aaa aaa ， ， ， 其邏輯結(jié)構(gòu)的二元組表示形式為：其邏輯結(jié)構(gòu)的二元組表示形式為： B= B=（D D，R R），其中：，其中： D=a1,a2,a9 R=ROW,COL ROW= , COL= , 1.2 基本概念與術(shù)語基本概念與術(shù)語 其實數(shù)據(jù)類型反映三個方面的內(nèi)容：其實數(shù)據(jù)類型反映三個方面的內(nèi)容： 存儲結(jié)構(gòu)，取值范圍和允許進(jìn)行的操作。存儲結(jié)構(gòu)，取值范圍和允許進(jìn)行的操作。 在用高級程序語言編寫的程序中，在用高級程序語言編寫的程序中， 每個數(shù)據(jù)都應(yīng)有一個每個數(shù)據(jù)都應(yīng)有一個所屬的、確定的數(shù)所屬的、確定的數(shù) 據(jù)類型。據(jù)類型。 1.2 基本概念與術(shù)語基本概念與

13、術(shù)語 在在JavaJava語言中，語言中，簡單數(shù)據(jù)簡單數(shù)據(jù)可描述為可描述為 JavaJava內(nèi)置的內(nèi)置的8 8種種基本的數(shù)據(jù)類型基本的數(shù)據(jù)類型之一；而之一；而 對于對于復(fù)雜數(shù)據(jù)復(fù)雜數(shù)據(jù)則可通過則可通過類的聲明類的聲明來引入來引入 新的數(shù)據(jù)類型。其中類的對象新的數(shù)據(jù)類型。其中類的對象(object)(object) 是新的類型的實例，類的成員變量確定是新的類型的實例，類的成員變量確定 了新的數(shù)據(jù)類型的數(shù)據(jù)表示方法和存儲了新的數(shù)據(jù)類型的數(shù)據(jù)表示方法和存儲 結(jié)構(gòu)，類的構(gòu)造函數(shù)和成員函數(shù)確定了結(jié)構(gòu)，類的構(gòu)造函數(shù)和成員函數(shù)確定了 新的數(shù)據(jù)類型的操作。新的數(shù)據(jù)類型的操作。 可用可用JavaJava語言中的

14、語言中的“數(shù)組數(shù)組”類型來類型來 實現(xiàn)實現(xiàn)順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)，用，用JavaJava語言中提供語言中提供 的的“對象引用對象引用”來實現(xiàn)來實現(xiàn)鏈?zhǔn)酱鎯Y(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)。 1.2 基本概念與術(shù)語基本概念與術(shù)語 例如：學(xué)生成績表基于數(shù)組的順序例如：學(xué)生成績表基于數(shù)組的順序 存儲結(jié)構(gòu)可描述如下：存儲結(jié)構(gòu)可描述如下： - -學(xué)生成績記錄的類描述學(xué)生成績記錄的類描述 package ch01; public class ResultsRecord private String studentNum; / 學(xué)號學(xué)號 private String studentName; / 學(xué)生姓名學(xué)生姓名 pri

15、vate float mathScore; / 數(shù)學(xué)分析數(shù)學(xué)分析 private float physicalScore; / 普通物理普通物理 private float algebraScore; / 普通物理普通物理 public String getStudentNum() return studentNum; public void setStudentNum(String studentNum) this.studentNum=studentNum; 1.2 基本概念與術(shù)語基本概念與術(shù)語 - -基于數(shù)組的順序存儲的類描述基于數(shù)組的順序存儲的類描述 package ch01; pub

16、lic class SqResults private ResultsRecord listElem； /存放學(xué)生成績的存儲空間存放學(xué)生成績的存儲空間 private int cluLen; / 當(dāng)前學(xué)生成績表的長度當(dāng)前學(xué)生成績表的長度 1.2 基本概念與術(shù)語基本概念與術(shù)語 以后將全部以后將全部采用采用JavaJava接口表示抽象數(shù)接口表示抽象數(shù) 據(jù)類型據(jù)類型。下面通過兩個具體實例來說明。下面通過兩個具體實例來說明 抽象數(shù)據(jù)類型的描述和實現(xiàn)。抽象數(shù)據(jù)類型的描述和實現(xiàn)。 抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型(Abstract Data Type,(Abstract Data Type, 簡稱簡稱ADT)AD

17、T)是指一是指一數(shù)據(jù)值數(shù)據(jù)值的集合和定義在的集合和定義在 這個集合上的一組這個集合上的一組操作操作。它不包括數(shù)據(jù)。它不包括數(shù)據(jù) 的計算機(jī)存儲表示，而且這里的操作是的計算機(jī)存儲表示，而且這里的操作是 脫離了具體實現(xiàn)的抽象操作，即不涉及脫離了具體實現(xiàn)的抽象操作，即不涉及 它的實現(xiàn)細(xì)節(jié)。它的實現(xiàn)細(xì)節(jié)。換句話說換句話說，抽象數(shù)據(jù)類，抽象數(shù)據(jù)類 型是指隱藏了數(shù)據(jù)的存儲結(jié)構(gòu)并且不涉型是指隱藏了數(shù)據(jù)的存儲結(jié)構(gòu)并且不涉 及操作的實現(xiàn)細(xì)節(jié)的數(shù)據(jù)類型。及操作的實現(xiàn)細(xì)節(jié)的數(shù)據(jù)類型。 1.2 基本概念與術(shù)語基本概念與術(shù)語 /復(fù)數(shù)抽象數(shù)據(jù)類型的接口表示復(fù)數(shù)抽象數(shù)據(jù)類型的接口表示 public interface ICo

18、mplex public double getReal(); / 取實部取實部 public void setReal(double real); / 修改實部修改實部 public double getImag(); / 取虛部取虛部 public void setImag(double imag); / 修改虛部修改虛部 public void add(IComplex Z); / 兩個實數(shù)的求和兩個實數(shù)的求和 1.2 基本概念與術(shù)語基本概念與術(shù)語 public class Complex implements IComplex private double real; / 實部實部 pr

19、ivate double imag; / 虛部虛部 / 構(gòu)造一個實數(shù)構(gòu)造一個實數(shù) public (double real, double imag) this.real = real; this.imag = imag; / 取實部取實部 public double return real; 1.2 基本概念與術(shù)語基本概念與術(shù)語 public class Complex implements IComplex / 修改實部修改實部 public void (double real) this.real = real; / 取虛部取虛部 public double getImag() retur

20、n imag; / 修改虛部修改虛部 public void (double imag) this.imag = imag; 1.2 基本概念與術(shù)語基本概念與術(shù)語 public class Complex implements IComplex / 兩個實數(shù)的求和兩個實數(shù)的求和 public void (IComplex Z) if (Z != null) real += Z.getReal(); imag += Z.getImag(); 1.3 算法與算法分析算法與算法分析 l算法的基本概念算法的基本概念 l算法的描述算法的描述 l算法分析算法分析 1.3 算法與算法分析算法與算法分析 何謂

21、算法？何謂算法？ 算法算法是是對特定問題求解步驟的一種對特定問題求解步驟的一種 描述，是指令的有限序列。其中每條指描述，是指令的有限序列。其中每條指 令表示一個或多個操作令表示一個或多個操作。嚴(yán)格來講，一。嚴(yán)格來講，一 個算法一般應(yīng)具有以下個算法一般應(yīng)具有以下5 5種性質(zhì)：種性質(zhì)： 1 1有窮性有窮性 2 2確定性確定性 3 3有效性有效性 4 4輸入輸入 5 5輸出輸出 1.3 算法與算法分析算法與算法分析 算法設(shè)計的目標(biāo)算法設(shè)計的目標(biāo): : 設(shè)計算法時，通常應(yīng)考慮達(dá)到以下設(shè)計算法時，通常應(yīng)考慮達(dá)到以下 目標(biāo)：目標(biāo)： 1正確性正確性 2. . 可讀性可讀性 3健壯性健壯性 4高效率高效率（時

22、間與空間）（時間與空間） 1.3 算法與算法分析算法與算法分析 本教程描述算法全部采用本教程描述算法全部采用JavaJava程序程序 設(shè)計語言設(shè)計語言。 【例例1 1】給出求整型數(shù)組給出求整型數(shù)組a a中最大值的中最大值的 算法算法 。 public static int maxEle(int a) int n=a.length; int max=a0; for (int i=1;in;i+) if (maxai) max=ai; return max; 1.3 算法與算法分析算法與算法分析 【例例2 2】給出將整型數(shù)組給出將整型數(shù)組a中數(shù)據(jù)元素中數(shù)據(jù)元素 實現(xiàn)就地逆置的算法實現(xiàn)就地逆置的算法

23、 。 public static void reverse(int a) int n=a.length; int temp; for (int i=0,j=n-1; ij; i+,j-) temp=ai; ai=aj; aj=temp; 1.3 算法與算法分析算法與算法分析 算法分析算法分析算法復(fù)雜度的評判算法復(fù)雜度的評判 算法復(fù)雜度算法復(fù)雜度 時間時間復(fù)雜度復(fù)雜度 空間空間復(fù)雜度復(fù)雜度 1.3 算法與算法分析算法與算法分析 l時間復(fù)雜度時間復(fù)雜度 通常有兩種衡量算法時間通常有兩種衡量算法時間( (效率效率) )的方法的方法: : 事后統(tǒng)計法事后統(tǒng)計法 事前分析估算法事前分析估算法 缺點(diǎn)：缺點(diǎn)

24、：1 1必須執(zhí)行程序必須執(zhí)行程序 2 2其它因素掩蓋算法本質(zhì)其它因素掩蓋算法本質(zhì) 1.3 算法與算法分析算法與算法分析 和算法執(zhí)行時間相關(guān)的因素：和算法執(zhí)行時間相關(guān)的因素： 1 1算法選用的策略算法選用的策略 2 2問題的規(guī)模問題的規(guī)模 3 3編寫程序的語言編寫程序的語言 4 4編譯程序產(chǎn)生的機(jī)器代碼的質(zhì)量編譯程序產(chǎn)生的機(jī)器代碼的質(zhì)量 5 5計算機(jī)執(zhí)行指令的硬件速度計算機(jī)執(zhí)行指令的硬件速度 6 6程序運(yùn)行的軟件環(huán)境程序運(yùn)行的軟件環(huán)境 l時間復(fù)雜度時間復(fù)雜度 1.3 算法與算法分析算法與算法分析 一個特定一個特定算法的算法的“運(yùn)行工作量運(yùn)行工作量” 的大小，只依賴于的大小，只依賴于問題的規(guī)模問題

25、的規(guī)模（通常用（通常用 整數(shù)量整數(shù)量n n表示），或者說，表示），或者說，它是問題規(guī)模它是問題規(guī)模 的函數(shù)。的函數(shù)。假如，記為假如，記為T T(n),并將稱并將稱T (n) T (n) 為算法的為算法的時間復(fù)雜度。時間復(fù)雜度。 【定義】【定義】 算法的時間復(fù)雜度算法的時間復(fù)雜度 T (n) = O(f(n) 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)存在正常數(shù)存在正常數(shù)c c和和N N，對所有的，對所有的 n(n n(nN)N)滿足滿足0 0T(n) T(n) c cf(n)f(n)。 例如：例如：T(n)=4n3+3n2+2n+1= O(n3)? 其中其中c=10,N=1c=10,N=1 1.3 算法與算法分析算法與

26、算法分析 如何估算如何估算 算法的時間復(fù)雜度？算法的時間復(fù)雜度？ 1.3 算法與算法分析算法與算法分析 算法算法 = = 控制結(jié)構(gòu)控制結(jié)構(gòu) + + 原操作原操作 （固有數(shù)據(jù)類型的操作） 算法的執(zhí)行時間算法的執(zhí)行時間 = = 原操作原操作(i)(i)的執(zhí)行次數(shù)的執(zhí)行次數(shù)原操作原操作(i)(i)的執(zhí)行時間的執(zhí)行時間 算法的執(zhí)行時間算法的執(zhí)行時間 與與 原操作執(zhí)行次數(shù)之和原操作執(zhí)行次數(shù)之和 成正比成正比 1.3 算法與算法分析算法與算法分析 【例例1 1】變量計量變量計量 x = 0 ; y = 0 ; s = 0 ; for(k=1;k=n;+k) +x;s+=x; for(i=1;i=n;+i)

27、 for(j=1;j=n;+j) +y;s+=y; 語句頻度語句頻度 n+1 n n+1 n(n+1) n2 T(n)=O(n2) 1.3 算法與算法分析算法與算法分析 【例例2 2】兩個矩陣相乘兩個矩陣相乘 public static void squareMult (int a, int b, int c, int n) for (int i=0;jn;j+) for (int j=0;jn;j+) cij=0; for (int k=0;kn;k+) cij+=aik*bkj; 語句頻度語句頻度 n n n(n+1)n(n+1) n n2 2 n n2 2(n+1)(n+1) n n3

28、3 T(n)=O(n3) 1.3 算法與算法分析算法與算法分析 從算法中選取一種對于所研究的從算法中選取一種對于所研究的 問題來說是問題來說是 關(guān)鍵操作關(guān)鍵操作 的原操作，以的原操作，以 該關(guān)鍵操作該關(guān)鍵操作 在算法中重復(fù)執(zhí)行的次在算法中重復(fù)執(zhí)行的次 數(shù)（語句頻度）數(shù)（語句頻度） 作為算法運(yùn)行時間作為算法運(yùn)行時間 的衡量準(zhǔn)則。的衡量準(zhǔn)則。 1.3 算法與算法分析算法與算法分析 【例例3 3】求下列算法的關(guān)鍵求下列算法的關(guān)鍵操作語句的語句頻操作語句的語句頻 度及算法的時間復(fù)雜度度及算法的時間復(fù)雜度 public static myOut() for (i=1; i=n; i=10*i) prin

29、tf(%4d, i); 解：解：設(shè)關(guān)鍵操作語句的語句頻度為設(shè)關(guān)鍵操作語句的語句頻度為f(n), 則有則有10f(n) n,所以所以 f(n) log10n 故故: T(n)=O(log10n) 1.3 算法與算法分析算法與算法分析 有些算法在規(guī)模相同的情況之下，有些算法在規(guī)模相同的情況之下， 其語句頻度會因輸入的其語句頻度會因輸入的數(shù)據(jù)值數(shù)據(jù)值或輸入或輸入 的的數(shù)據(jù)順序數(shù)據(jù)順序不同而不同，則時間復(fù)雜不同而不同，則時間復(fù)雜 度也會不同，為此有度也會不同，為此有最好最好、最壞最壞和和平平 均均時間復(fù)雜度之分。時間復(fù)雜度之分。 1.3 算法與算法分析算法與算法分析 【例例4 4】如下算法如下算法實現(xiàn)

30、的功能是在數(shù)組實現(xiàn)的功能是在數(shù)組a0:n-1a0:n-1 中查找值為中查找值為x x的數(shù)據(jù)元素。若找到，則返回的數(shù)據(jù)元素。若找到，則返回x x在在 a a中的位置；否則，返回中的位置；否則，返回-1-1。求其時間復(fù)雜度求其時間復(fù)雜度。 public static int rSearch(int a,int x) int n=a.length; for(int i=0; ini+); if (i=n) return -1; else return i; 最好最好時間復(fù)雜度：O(1) 最壞最壞時間復(fù)雜度：O(n) 平均平均時間復(fù)雜度：O(n) 1.3 算法與算法分析算法與算法分析 【例例5 5】如

31、下算法是用冒泡排序法對數(shù)組如下算法是用冒泡排序法對數(shù)組a a中的中的 n n個整型數(shù)據(jù)元素進(jìn)行排序，求該算法的時間個整型數(shù)據(jù)元素進(jìn)行排序，求該算法的時間 復(fù)雜度。復(fù)雜度。 public static void bubbleSort(int a, int n) int temp,flag=1; for (int i=1;in i+) flag=0; for (int j=0;jaj+1) flag=1; temp=aj; aj=aj+1; aj+1=tmep; 最好最好時間復(fù)雜度：O(n) 最壞最壞時間復(fù)雜度：O(n2) 1.3 算法與算法分析算法與算法分析 按增長率由小至大的順序排列有：按增長

32、率由小至大的順序排列有： 注意注意 多項式時間算法多項式時間算法的時間復(fù)雜度： O(1)O(log2n)O(n)O(nlog2n)O(n2)O(n3) 指數(shù)時間算法指數(shù)時間算法的時間復(fù)雜度： O(2n)O(n!)O(nn) 總之，總之，隨著的增大，指數(shù)時間算法和多項式時隨著的增大，指數(shù)時間算法和多項式時 間算法在所需時間上間算法在所需時間上相差非常懸殊相差非常懸殊。 1.3 算法與算法分析算法與算法分析 【問題描述問題描述】給定一整數(shù)序列給定一整數(shù)序列A A1 1， A A2 2，. A. An n （可能有負(fù)數(shù)），求（可能有負(fù)數(shù)），求A A1 1A An n的一個子序列的一個子序列A Ai

33、iA Aj j， 使得使得A Ai i到到A Aj j的和最大。例如：整數(shù)序列的和最大。例如：整數(shù)序列 -2, 11, -2, 11, -4, 13, -5, 2, -5, -3, 12, -9-4, 13, -5, 2, -5, -3, 12, -9的最大子序的最大子序 列的和為列的和為2121（從（從A A2 2到到A A9 9）。）。 下面介紹四種實現(xiàn)方法下面介紹四種實現(xiàn)方法 1.3 算法與算法分析算法與算法分析 public static int maxSub_1(int sequence) int max = 0; int n= sequence.length; int sum =

34、0; /第一重循環(huán)執(zhí)行一次則計算出長度為第一重循環(huán)執(zhí)行一次則計算出長度為i的所有子序列和的最大值的所有子序列和的最大值 for (int i = 1; i = n; i+) for (int j = 0; j n; j+) sum = 0; for (int k = j; k j + i return max; 時間復(fù)雜度時間復(fù)雜度: O(n3) 1.3 算法與算法分析算法與算法分析 public static int maxSub_2(int sequence) int max = 0; int n= sequence.length; int sum = 0; for (int i = 0;

35、 i n; i+) sum = 0; for (int j = i; j max) max = sum; return max; 時間復(fù)雜度時間復(fù)雜度: O(n2) 1.3 算法與算法分析算法與算法分析 public static int maxSum(int sequence) if (left=right) if (sequence left0) return sequeneceleft; else return 0; int mid=(left+right)/2; int maxLeftSum=maxSum(sequenece,left,mid); int maxRightSum=max

36、Sum(sequenece,mid+1,right); int maxLeftBorderSum=0,leftBorderSum=0; for(int i=mid; i=left; i-) leftBorderSum+= sequence i; if(leftBorderSummaxLeftBorderSum) maxLeftBorderSum=leftBorderSum; 1.3 算法與算法分析算法與算法分析 public static int maxSum(int sequence) int maxRightBorderSum=0,rightBorderSum=0; for(int i=m

37、id+1; imaxRightBorderSum) maxRightBorderSum=rightBorderSum; return max3(maxLeftSum,maxRightSum, maxLeftBorderSum+maxRightBorderSum); 時間復(fù)雜度時間復(fù)雜度: O(nlog2n) 1.3 算法與算法分析算法與算法分析 public static int max3( int a,int b,int c) int max=ab:a?b; max=maxc:max?c; retrun max; public static int maxSub_3( int sequenc

38、e) return maxSum(a,0, sequence.length-1); 1.3 算法與算法分析算法與算法分析 public static int maxSub_4(int sequence) int max = 0; int n= sequence.length; int sum = 0; for (int i = 0; i max) max = sum; else if (sum 0) sum = 0; return max; 時間復(fù)雜度時間復(fù)雜度: O(n) 1.4 Java提供的泛型方法提供的泛型方法 若若除去除去數(shù)據(jù)對象的基本數(shù)據(jù)對象的基本類型外類型外，實現(xiàn)，實現(xiàn) 方法相同方法相同的，則可用泛型方法來描述這的，則可用泛型方法來描述這 種基本功能。種基本功能。 1.1.使用使用ObjectObject表示