1、數據結構與算法數據結構與算法(C#語言描述語言描述)信息管理與信息系統專業信息管理與信息系統專業授課教師：呂雅麗授課教師：呂雅麗第第1章章 緒論緒論 數據結構數據結構課程通過介紹一些典型數據結構的特性來討課程通過介紹一些典型數據結構的特性來討論基本的數據組織和數據處理方法。論基本的數據組織和數據處理方法。 目的：目的：學習數據結構的基本概念和必要的基礎知識。學習數據結構的基本概念和必要的基礎知識。理解邏輯結構、存儲結構和運算的關系。理解邏輯結構、存儲結構和運算的關系。學會分析研究計算機加工的數據結構的特性，掌握常學會分析研究計算機加工的數據結構的特性，掌握常用的數據結構的特點并能正確地選擇數據

2、結構。用的數據結構的特點并能正確地選擇數據結構。為應用涉及的數據選擇適當的邏輯結構和存儲結構，為應用涉及的數據選擇適當的邏輯結構和存儲結構，并能設計出較高質量的算法。并能設計出較高質量的算法。1.1 什么是數據結構什么是數據結構 1.1.1 數據結構的定義數據結構的定義用計算機解決一個具體的問題時，大致需要經過以用計算機解決一個具體的問題時，大致需要經過以下幾個步驟：下幾個步驟：（1）分析問題，確定數據模型。）分析問題，確定數據模型。（2）設計相應的算法。）設計相應的算法。（3）編寫程序，運行并調試程序直至得到正確的結果）編寫程序，運行并調試程序直至得到正確的結果。數據數據是描述客觀事物的數、

3、字符以及所有能輸入到計是描述客觀事物的數、字符以及所有能輸入到計算機中并被計算機程序處理的符號的集合。算機中并被計算機程序處理的符號的集合。通常以通常以數據元素數據元素作為數據的基本單位，也就是說數據作為數據的基本單位，也就是說數據元素是組成數據的、有一定意義的基本單位，在計算機中元素是組成數據的、有一定意義的基本單位，在計算機中通常作為整體處理，有些情況下數據元素也稱為元素、結通常作為整體處理，有些情況下數據元素也稱為元素、結點、記錄等。點、記錄等。有時候，一個數據元素可以由若干個有時候，一個數據元素可以由若干個數據項數據項組成。數組成。數據項是具有獨立含義的數據最小單位，也稱為字段或域。據

4、項是具有獨立含義的數據最小單位，也稱為字段或域。數據對象數據對象是性質相同的有限個數據元素的集合，它是數據是性質相同的有限個數據元素的集合，它是數據的一個子集，如：的一個子集，如：大寫字母數據對象是集合大寫字母數據對象是集合C=A,B,C,，Z；1100的整數數據對象是集合的整數數據對象是集合N=1,2, ,100。默認情況下，數據結構中的數據都指的是數據對象。默認情況下，數據結構中的數據都指的是數據對象。數據結構數據結構是指所有數據元素以及數據元素之間的關系，是指所有數據元素以及數據元素之間的關系，可以看作是相互之間存在著特定關系的數據元素的集合，因可以看作是相互之間存在著特定關系的數據元素

5、的集合，因此，可時把數據結構看成是帶結構的數據元素的集合。數據此，可時把數據結構看成是帶結構的數據元素的集合。數據結構包括如下幾個方面：結構包括如下幾個方面：（1）數據元素之間的邏輯關系，即）數據元素之間的邏輯關系，即數據的邏輯結構數據的邏輯結構，它是數據結構在用戶面前呈現的形式。它是數據結構在用戶面前呈現的形式。（2）數據元素及其關系在計算機存儲器中的存儲方式，）數據元素及其關系在計算機存儲器中的存儲方式，即即數據的存儲結構數據的存儲結構，也稱為，也稱為數據的物理結構數據的物理結構。（3）施加在該數據上的操作，即）施加在該數據上的操作，即數據的運算數據的運算。1.1.2 數據的邏輯結構數據的

6、邏輯結構數據的邏輯結構數據的邏輯結構是用戶根據需要建立起來的數據組織是用戶根據需要建立起來的數據組織形式，它反映數據元素之間的邏輯關系而不是物理關系，形式，它反映數據元素之間的邏輯關系而不是物理關系，是獨立于計算機的。是獨立于計算機的。數據中數據元素之間可以有不同的邏輯關系數據中數據元素之間可以有不同的邏輯關系 。【例例1.1】 一個學生高等數學成績單如表一個學生高等數學成績單如表1.1所示。這個所示。這個表中的數據元素是學生成績記錄，每個數據元素由表中的數據元素是學生成績記錄，每個數據元素由3個數據個數據項（即學號、姓名和分數）組成。討論其邏輯結構特性。項（即學號、姓名和分數）組成。討論其邏

7、輯結構特性。學號學號姓名姓名分數分數2011001王華王華902011010劉麗劉麗622011006陳明陳明542011009張強張強952011007許兵許兵762011012李萍李萍882011005李英李英82表表1.1 高等數學成績單高等數學成績單線性結構線性結構【例例1.2】 某高校組織結構示意圖如圖某高校組織結構示意圖如圖1.1所示。高校下設所示。高校下設若干個學院和若干個處，每個學院下設若干個系，每個處下設若干個學院和若干個處，每個學院下設若干個系，每個處下設若干個科或辦公室。討論其邏輯結構特性。若干個科或辦公室。討論其邏輯結構特性。圖圖1.1 某高校組織結構示意圖某高校組織結

8、構示意圖樹形結構樹形結構【例例1.3】 全國部分城市交通線路圖如圖全國部分城市交通線路圖如圖1.2所示。所示。討論其邏輯結構特性。討論其邏輯結構特性。圖圖1.2 全國部分城市交通線路圖全國部分城市交通線路圖圖形結構圖形結構歸納起來，數據的邏輯結構有歸納起來，數據的邏輯結構有4種：種：集合：數據元素沒有任何相鄰關系。集合：數據元素沒有任何相鄰關系。線性結構線性結構樹形結構樹形結構圖形結構圖形結構為了更通用地描述數據的邏輯結構，通常采用為了更通用地描述數據的邏輯結構，通常采用二元組二元組表示表示數據的邏輯結構，一個二元組如下：數據的邏輯結構，一個二元組如下：B=(D,R)其中，其中，B是一種數據結

9、構，是一種數據結構，D是數據元素的集合，在是數據元素的集合，在D上數據元上數據元素之間可能存在多種關系，素之間可能存在多種關系，R是所有關系的集合。即：是所有關系的集合。即：D=di | 1in，n0R=rj | 1jm，m0R中的某個關系中的某個關系rj（1jm）是序偶的集合，對于）是序偶的集合，對于rj中的任一中的任一序偶序偶（x，yD），把），把x叫做序偶的第一結點，把叫做序偶的第一結點，把y叫做序偶叫做序偶的第二結點，又稱序偶的第一結點為第二結點的的第二結點，又稱序偶的第一結點為第二結點的前驅結點前驅結點，稱第，稱第二結點為第一結點的二結點為第一結點的后繼結點后繼結點。如在如在的序偶中

10、，的序偶中，x為為y的前驅結點，而的前驅結點，而y為為x的后繼結點。的后繼結點。若某個結點沒有前驅結點，則稱該結點為若某個結點沒有前驅結點，則稱該結點為開始結點開始結點；若某個；若某個結點沒有后繼結點，則稱該結點為結點沒有后繼結點，則稱該結點為終端結點終端結點。對于對稱序偶，即滿足這樣的條件：若對于對稱序偶，即滿足這樣的條件：若r（rR），），則則r（x，yD），可用圓括號代替尖括號，即），可用圓括號代替尖括號，即(x,y)r。【例例1.4】 采用二元組表示前面三個例子的邏輯結構。采用二元組表示前面三個例子的邏輯結構。解：解：高等數學成績單（假設學號為關鍵字）的二元組表示高等數學成績單（假設學

11、號為關鍵字）的二元組表示如下：如下：學號學號姓名姓名分數分數2011001王華王華902011010劉麗劉麗622011006陳明陳明542011009張強張強952011007許兵許兵762011012李萍李萍882011005李英李英82B1=(D,R)D=2011001,2011010,2011006,2011009,2011007,2011012,2011005R=r1/表示只有一種邏輯關系表示只有一種邏輯關系r1=, ,等價表示等價表示某高校組織結構（假設單位名為關鍵字）的二元組表示如下：某高校組織結構（假設單位名為關鍵字）的二元組表示如下：B2=(D,R)D=XX大學大學,計算機學

12、院計算機學院,電子信息學院電子信息學院,教務處教務處,學生處學生處,科學系科學系,工工程系程系,應用系應用系, 招生辦招生辦,就業辦就業辦R=r1r1=, , , 等價表示等價表示全國部分城市交通圖（假設城市名為關鍵字）的二元組全國部分城市交通圖（假設城市名為關鍵字）的二元組表示如下：表示如下：B3=(D,R)D=北京北京,鄭州鄭州,武漢武漢,長沙長沙,南京南京,南昌南昌,杭州杭州,上海上海R=r1r1=(北京北京,鄭州鄭州),(北京北京,南京南京),(鄭州鄭州,武漢武漢),(武漢武漢,南京南京),(武漢武漢,長沙長沙), (南京南京,南昌南昌),(南京南京,上海上海),(南京南京,杭州杭州)

13、,(南昌南昌,杭州杭州),(南昌南昌,上海上海)等價表示等價表示1.1.3 數據的存儲結構數據的存儲結構數據的存儲結構數據的存儲結構應正確地反映數據元素之間的邏輯關系，應正確地反映數據元素之間的邏輯關系，也就是說，在設計某種邏輯結構對應的存儲結構時，不僅要也就是說，在設計某種邏輯結構對應的存儲結構時，不僅要存儲所有的數據元素，還要存儲數據元素之間的關系。存儲所有的數據元素，還要存儲數據元素之間的關系。所以將所以將數據的存儲結構稱為邏輯結構的映像數據的存儲結構稱為邏輯結構的映像，設計數據，設計數據的存儲結構稱為從邏輯結構到存儲器的映射，如圖的存儲結構稱為從邏輯結構到存儲器的映射，如圖1.4所示。

14、所示。【例例1.5】 對于表對于表1.1所示高等數學成績單，設計多種存儲所示高等數學成績單，設計多種存儲結構，并討論各種存儲結構的特性。結構，并討論各種存儲結構的特性。解：解：這里設計高等數學成績單的兩種存儲結構。這里設計高等數學成績單的兩種存儲結構。存儲結構存儲結構1：用用C#語言中的數組來存儲高等數學成績單，語言中的數組來存儲高等數學成績單，設計存放學生成績記錄的數組類型如下：設計存放學生成績記錄的數組類型如下：struct Stud1/學生成績記錄類型學生成績記錄類型public int no;/存放學號存放學號public string name;/存放姓名存放姓名public dou

15、ble score;/存放分數存放分數const int MaxSize = 100;/存放最多記錄個數存放最多記錄個數Stud1 st=new Stud1MaxSize;/存放記錄的數組存放記錄的數組st0.no=2011001; =王華王華; st0.score=90;st1.no=2011010; =劉麗劉麗; st1.score=62;st2.no=2011006; =陳明陳明; st2.score=54;st3.no=2011009; =張強張強; st3.score=95;st4.no=2011007; st4.nam

16、e=許兵許兵; st4.score=76;st5.no=2011012; =李萍李萍; st5.score=88;st6.no=2011005; =李英李英; st6.score=82;順序存儲結構順序存儲結構定義一個數組定義一個數組st用于存放高等數學成績單如下：用于存放高等數學成績單如下：存儲結構存儲結構2：用用C#語言中的單鏈表來存儲高等數學成績語言中的單鏈表來存儲高等數學成績單，設計存放學生成績記錄的結點類型如下：單，設計存放學生成績記錄的結點類型如下：class Stud2/學生成績單鏈表結點類學生成績單鏈表結點類public int no;/存放學號

17、存放學號public string name;/存放姓名存放姓名public double score;/存放分數存放分數public Stud2 next;/存放下一個結點指針存放下一個結點指針Stud2 head;/學生單鏈表開始結點學生單鏈表開始結點Stud2 p1, p2, p3, p4, p5, p6, p7;p1=new Stud2();p1.no=2011001; =王華王華; p1.score=90;p2=new Stud2();p2.no=2011010; =劉麗劉麗; p2.score=62;p3=new Stud2();p3.no=201100

18、6; =陳明陳明; p3.score=54;p4=new Stud2();p4.no=2011009; =張強張強; p4.score=95;p5=new Stud2();p5.no=2011007; =許兵許兵; p5.score=76;p6=new Stud2();p6.no=2011012; =李萍李萍; p6.score=88;p7=new Stud2();p7.no=2011005; =李英李英; p7.score=82;head=p1;/建立結點之間的關系建立結點之間的關系p1.next=p2;p2.next=p

19、3;p3.next=p4;p4.next=p5;p5.next=p6;p6.next=p7;p7.next=null;建立一個用于存放高等數學成績單的單鏈表（開始結點為建立一個用于存放高等數學成績單的單鏈表（開始結點為head）如下：）如下：鏈式存儲結構鏈式存儲結構說明：說明：C/C+語言中具有指針類型，嚴格上講語言中具有指針類型，嚴格上講C#語言中語言中沒有指針類型，但沒有指針類型，但C#中有對象引用機制，可以間接地實現指中有對象引用機制，可以間接地實現指針的某些作用。為了和采用針的某些作用。為了和采用C/C+描述數據結構相一致，本描述數據結構相一致，本書也將對象引用稱為指針。書也將對象引用

20、稱為指針。Stud2 head，p1;headp1p1=new Stud2();對象實例對象實例head=p1;歸納起來有以下歸納起來有以下4種常用的存儲結構類型：種常用的存儲結構類型：（1）順序存儲結構）順序存儲結構（2）鏈式存儲結構）鏈式存儲結構（3）索引存儲結構）索引存儲結構（4）哈希（或散列）存儲結構）哈希（或散列）存儲結構1.1.4 數據的運算數據的運算將數據存放在計算機中的目的是為了實現一種或多將數據存放在計算機中的目的是為了實現一種或多種運算。運算包括種運算。運算包括功能描述功能描述和和功能實現功能實現，前者是基于邏，前者是基于邏輯結構的，是用戶定義的，是抽象的；后者是基于存儲輯

21、結構的，是用戶定義的，是抽象的；后者是基于存儲結構的，是程序員用計算機語言或偽碼表示的，是詳細結構的，是程序員用計算機語言或偽碼表示的，是詳細的過程。的過程。例如，對于高等數學成績單這種數據結構，可以進例如，對于高等數學成績單這種數據結構，可以進行一系列的運算，如行一系列的運算，如增加一個學生成績記錄增加一個學生成績記錄、刪除一個刪除一個學生成績記錄學生成績記錄、求所有學生的平均分求所有學生的平均分，查找序號為查找序號為i的學的學生姓名和分數生姓名和分數等等。等等。同一運算，在不同存儲結構中的實現過程是不同的。例同一運算，在不同存儲結構中的實現過程是不同的。例如，查找序號為如，查找序號為i的學

22、生姓名和分數，其運算功能描述是：查的學生姓名和分數，其運算功能描述是：查找邏輯序號為找邏輯序號為i的學生成績記錄，若找到了，輸出其姓名和分的學生成績記錄，若找到了，輸出其姓名和分數，并返回數，并返回true；否則返回；否則返回false。但在順序存儲結構和鏈式。但在順序存儲結構和鏈式存儲結構中的實現過程不同的。存儲結構中的實現過程不同的。在順序存儲結構中對應的代碼如下：在順序存儲結構中對應的代碼如下：public bool Findi(int i,ref string na,ref double sc) /i為邏輯序號為邏輯序號if (in)/i錯誤時返回錯誤時返回false,n為數據元素個數

23、為數據元素個數return false;else/i正確時返回正確時返回truena=;sc=sti-1.score;return true;在鏈式存儲結構中對應的代碼如下：在鏈式存儲結構中對應的代碼如下：public bool Findi(int i,ref string na,ref double sc) /i為邏輯序號為邏輯序號int j=1;Stud2 p=head;while (ji & p!=null)j+;p=p.next;if (i=0 | p=null)/i錯誤時返回錯誤時返回falsereturn false;else/i正確時返回正確時返回tr

24、uena=;sc=p.score;return true;歸納起來，對于一種數據結構，其邏輯結構是唯一的歸納起來，對于一種數據結構，其邏輯結構是唯一的（盡管邏輯結構的表示形式有多種），但它可能對應多種存（盡管邏輯結構的表示形式有多種），但它可能對應多種存儲結構，并且在不同的存儲結構中，同一運算的實現過程可儲結構，并且在不同的存儲結構中，同一運算的實現過程可能不同。能不同。1.1.5 數據結構和數據類型數據結構和數據類型1. 數據類型數據類型在用高級程序語言（如在用高級程序語言（如C#語言）編寫的程序中，通常語言）編寫的程序中，通常需要對程序中出現的每個變量、常量或表達式，明確說明需

25、要對程序中出現的每個變量、常量或表達式，明確說明它們所屬的數據類型。不同類型的變量，其所能取的值的它們所屬的數據類型。不同類型的變量，其所能取的值的范圍不同，所能進行的操作不同。范圍不同，所能進行的操作不同。數據類型是一組性質相數據類型是一組性質相同的值的集合和定義在此集合上的一組操作的總稱。同的值的集合和定義在此集合上的一組操作的總稱。C#數據類型主要分為值類型和引用類型兩大類。數據類型主要分為值類型和引用類型兩大類。2. 抽象數據類型抽象數據類型抽象數據類型抽象數據類型（Abstract Data Type簡寫為簡寫為ADT）指的是）指的是用戶進行軟件系統設計時從問題的數學模型中抽象出來的

26、邏用戶進行軟件系統設計時從問題的數學模型中抽象出來的邏輯數據結構和邏輯數據結構上的運算，而不考慮計算機的具輯數據結構和邏輯數據結構上的運算，而不考慮計算機的具體存儲結構和運算的具體實現算法。體存儲結構和運算的具體實現算法。抽象數據類型中的數據對象和數據運算的聲明與數據對抽象數據類型中的數據對象和數據運算的聲明與數據對象的表示和數據運算的實現相互分離。象的表示和數據運算的實現相互分離。抽象數據類型可用（抽象數據類型可用（D,S,P）三元組表示。其中）三元組表示。其中D是是數據對象，數據對象，S是是D上的關系集，上的關系集，P是是D中數據運算的基本運中數據運算的基本運算集。其基本格式如下：算集。其

27、基本格式如下：ADT 抽象數據類型名抽象數據類型名 數據對象：數據對象的聲明數據對象：數據對象的聲明數據關系：數據關系的聲明數據關系：數據關系的聲明基本運算：基本運算的聲明基本運算：基本運算的聲明 ADT 抽象數據類型名抽象數據類型名【例例1.6】 構造集合構造集合ADT Set，假設其中元素為字符串類，假設其中元素為字符串類型，遵循標準數學定義，成員包括型，遵循標準數學定義，成員包括Create（創建一個空集（創建一個空集合）、合）、Insert（插入一個元素）、（插入一個元素）、Remove（刪除一個元素）、（刪除一個元素）、IsIn（一個元素是否屬于集合）。（一個元素是否屬于集合）。另外

28、定義一個實現集合運算的另外定義一個實現集合運算的ADT TwoSet，成員包括，成員包括Union（集合并）、（集合并）、IIntersection（集合交）和（集合交）和Difference（集合差）。（集合差）。解：解：抽象數據類型抽象數據類型Set和和TwoSet的定義如下：的定義如下：ADT Set/集合的抽象數據類型集合的抽象數據類型數據對象：數據對象： data = di | 1in,distring;/存放集合中元素存放集合中元素 int n;/集合中元素個數集合中元素個數 數據關系：數據關系： 無無 基本運算：基本運算： public void Create();/創建一個空的

29、集合創建一個空的集合 public bool IsIn(string e);/判斷判斷e是否在集合中是否在集合中 public bool Insert(string e);/將元素將元素e插入到集合中插入到集合中 public bool Remove(string e);/從集合中刪除元素從集合中刪除元素e ADT SetADT TwoSet/兩個集合運算的抽象數據類型兩個集合運算的抽象數據類型 數據對象：數據對象：Set set1;/集合集合set1Set set2;/集合集合set2 數據關系：數據關系：無無 基本運算：基本運算：public Set Union()/求兩集合的并集求兩集合

30、的并集public Set IIntersection()/求兩集合的交集求兩集合的交集public Set Difference()/求兩集合的差集求兩集合的差集抽象數據類型有兩個重要特征：數據抽象和數據封裝。抽象數據類型有兩個重要特征：數據抽象和數據封裝。所謂所謂數據抽象數據抽象，是指用，是指用ADT描述程序處理的實體時，描述程序處理的實體時，強調的是其本質的特征、其所能完成的功能以及它和外部強調的是其本質的特征、其所能完成的功能以及它和外部用戶的接口（即外界使用它的方法）。用戶的接口（即外界使用它的方法）。所謂所謂數據封裝數據封裝，是指將實體的外部特性和其內部實現，是指將實體的外部特性和

31、其內部實現細節分離，并且對外部用戶隱藏其內部實現細節。細節分離，并且對外部用戶隱藏其內部實現細節。1.2 算法及其描述算法及其描述1.2.1 什么是算法什么是算法數據元素之間的關系有邏輯關系和物理關系，對應的數據元素之間的關系有邏輯關系和物理關系，對應的運算有邏輯結構上的運算（抽象運算）和具體存儲結構上運算有邏輯結構上的運算（抽象運算）和具體存儲結構上的運算（運算實現）。算法是在具體存儲結構上實現某個的運算（運算實現）。算法是在具體存儲結構上實現某個抽象運算。抽象運算。確切地說，確切地說，算法算法是對特定問題求解步驟的一種描述，是對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令

32、表示計算機的一個它是指令的有限序列，其中每一條指令表示計算機的一個或多個操作。或多個操作。算法具有以下五個重要的特性：算法具有以下五個重要的特性：有窮性有窮性。指算法在執行有限的步驟之后，自動結束而不。指算法在執行有限的步驟之后，自動結束而不會出現無限循環，并且每一個步驟在可接受的時間內完會出現無限循環，并且每一個步驟在可接受的時間內完成。成。確定性確定性。對于每種情況下執行的操作，在算法中都有確。對于每種情況下執行的操作，在算法中都有確定的含義，不會出現二義性。并且在任何條件下，算法定的含義，不會出現二義性。并且在任何條件下，算法都只有一條執行路徑。都只有一條執行路徑。可行性可行性。算法的每

33、條指令都是基本可執行的，意指借助。算法的每條指令都是基本可執行的，意指借助紙、筆或計算機可以完成。紙、筆或計算機可以完成。有輸入有輸入。算法有零個或多個輸入。算法有零個或多個輸入。有輸出有輸出。算法至少有一個或多個輸出。算法至少有一個或多個輸出。1.2.2 算法描述算法描述下面介紹下面介紹C#語言中描述算法的相關內容。語言中描述算法的相關內容。1. 數據表示數據表示（1）字段）字段（2）構造函數）構造函數（3）方法）方法1.3 算法分析算法分析1.3.1 算法的特性和算法設計的目標算法的特性和算法設計的目標（1）正確性。）正確性。（2）可使用性。）可使用性。（3）可讀性。）可讀性。（4）健壯性

34、。）健壯性。（5）高效率與低存儲量需求。）高效率與低存儲量需求。 1.3.2 算法時間效率分析算法時間效率分析求解同一問題可能對應多種算法，例如求求解同一問題可能對應多種算法，例如求s=1+2+n，其中其中n為正整數，通常有以下兩種算法為正整數，通常有以下兩種算法fun1(n)和和fin2(n)，顯然，顯然前者算法的時間效率不如后者。前者算法的時間效率不如后者。一個算法是由一個算法是由控制結構控制結構（順序、分支和循環（順序、分支和循環3種）和原操種）和原操作（指固有數據類型的操作）構成的，算法的運行時間取決于作（指固有數據類型的操作）構成的，算法的運行時間取決于兩者的綜合效果。兩者的綜合效果

35、。例如，如下所示是在某個類中定義的例如，如下所示是在某個類中定義的Solve方法，其中形方法，其中形參參a是一個是一個m行行n列的數組，當是一個方陣（列的數組，當是一個方陣（m=n）時求主對角）時求主對角線所有元素之和并返回線所有元素之和并返回true，否則返回，否則返回false，從中看到該算法，從中看到該算法由由4部分組成，包含兩個順序結構、一個分支結構和一個循環部分組成，包含兩個順序結構、一個分支結構和一個循環結構。結構。為了便于比較求解同一問題的不同算法，通常的做法是，為了便于比較求解同一問題的不同算法，通常的做法是，從算法中選取一種對于所討論的問題來說是基本運算的原操從算法中選取一種

36、對于所討論的問題來說是基本運算的原操作，作，算法執行時間大致為這種原操作所需的時間與其運算次算法執行時間大致為這種原操作所需的時間與其運算次數數（一個語句的運行次數稱為語句頻度）的乘積。被視為算（一個語句的運行次數稱為語句頻度）的乘積。被視為算法基本運算的原操作一般是最深層循環內的語句（法基本運算的原操作一般是最深層循環內的語句（Solve算法算法中的基本運算為中的基本運算為s+=ai,i）。）。顯然，在一個算法中，執行基本運算的原操作的次數越顯然，在一個算法中，執行基本運算的原操作的次數越少，其運行時間也就相對地越少；反之其運行時間也就相對少，其運行時間也就相對地越少；反之其運行時間也就相對地越多。也就是說，地越多。也就是說，一個算法的執行時間可以看成是其中基一個算法的執行時間可以看成是其中基本運算的原操作的執行次數本運算的原操作的執行次數。 一個算法的執行基本運算次數一個算法的執行基本運算次數T(n)是問題規模是問題規模n的某個函的某個函數數f(n)，記作：，記作：T(n)=O(f(n)記號記號“O”讀作讀作“大大O”（是（是Order的簡寫，意指數量級），它的簡寫，意指數量級），它表示隨問題規模表示隨問題規模n的增大算法執行時間的增長率和的增大算法執行時間的增長率和f(n)的增長率的增長率相同。相同。T