《數(shù)據(jù)結(jié)構(gòu)》課件1第2章概述

主要學(xué)習(xí)內(nèi)容數(shù)據(jù)結(jié)構(gòu)相關(guān)概念12數(shù)據(jù)結(jié)構(gòu)課程學(xué)習(xí)的內(nèi)容3算法性能分析4算法及特點(diǎn)數(shù)據(jù)結(jié)構(gòu)相關(guān)概念1、數(shù)據(jù)2、數(shù)據(jù)元素3、數(shù)據(jù)項(xiàng)4、數(shù)據(jù)對象5、數(shù)據(jù)結(jié)構(gòu)邏輯結(jié)構(gòu)存儲結(jié)構(gòu)概念數(shù)據(jù)(Data)所有能輸入到計(jì)算機(jī)中，并被計(jì)算機(jī)識別和處理的符號的總稱。數(shù)值型數(shù)據(jù)：整數(shù)、實(shí)數(shù)等；非數(shù)值型數(shù)據(jù)：字符、文本、聲音、圖像、視頻等；數(shù)據(jù)是計(jì)算機(jī)程序加工的原料，是信息的編碼表示。文字翻譯程序處理的數(shù)據(jù)是各國語言文本字符串；視頻編輯軟件則處理的是視頻、圖片、音樂等多媒體數(shù)據(jù)。數(shù)據(jù)元素(DataElement)數(shù)據(jù)集合中的一個(gè)個(gè)體。是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常將其作為一個(gè)邏輯整體進(jìn)行處理。如一個(gè)整數(shù)30，一個(gè)字符串"helloworld"，一個(gè)商品，一節(jié)講課視頻等。在不同場合下，數(shù)據(jù)元素也常被稱為元素、結(jié)點(diǎn)、頂點(diǎn)和記錄等。當(dāng)一個(gè)數(shù)據(jù)元素包含有多個(gè)部分信息時(shí)，通常被稱為記錄。當(dāng)一個(gè)數(shù)據(jù)元素（記錄）包含有多個(gè)部分信息時(shí)，其中每個(gè)部分的信息被稱為一個(gè)數(shù)據(jù)項(xiàng)。如一件商品的記錄可能包含商品名稱、編號、類別、價(jià)格等多個(gè)數(shù)據(jù)項(xiàng)。數(shù)據(jù)項(xiàng)是構(gòu)成數(shù)據(jù)元素的不可分割的最小單位，也被稱為字段、域或?qū)傩?。?shù)據(jù)項(xiàng)(DataItem)數(shù)據(jù)對象(DataObject)數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。例如，整數(shù)的數(shù)據(jù)對象是集合{0,±1,±2,…}，英文字母的數(shù)據(jù)對象是集合{'a','A','b','B',…}。在具體應(yīng)用中，一個(gè)數(shù)據(jù)對象中的元素通常相互之間存在某種關(guān)系。相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合；帶關(guān)系的數(shù)據(jù)元素的集合（Collectionofrelationaldataelements）。數(shù)據(jù)結(jié)構(gòu)（DataStructure）結(jié)構(gòu)=實(shí)體+關(guān)系數(shù)據(jù)結(jié)構(gòu)=數(shù)據(jù)元素+關(guān)系A(chǔ)B最外面的大圓圈表示數(shù)據(jù)這個(gè)大集合；標(biāo)識為A和B的兩個(gè)圓圈分別表示2個(gè)數(shù)據(jù)對象集合；除此之外的各圓圈表示各種不同大小的數(shù)據(jù)元素；數(shù)據(jù)對象A、B中分別包含若干相同類型的數(shù)據(jù)元素；B數(shù)據(jù)對象中的數(shù)據(jù)元素之間存在關(guān)系，即形成了一種數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)的層次數(shù)據(jù)結(jié)構(gòu)的概念由C.A.R.Hoare和N.Wirth在1966年提出。Algorithms+DataStructures=Programs

---N.Wirth1976年提出。精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來更高的運(yùn)行效率。實(shí)現(xiàn)大型的復(fù)雜程序，必須對程序所處理的數(shù)據(jù)結(jié)構(gòu)進(jìn)行深入研究。數(shù)據(jù)結(jié)構(gòu)（DataStructure）數(shù)據(jù)結(jié)構(gòu)是帶關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)的2個(gè)層面：邏輯結(jié)構(gòu)存儲結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)（DataStructure）邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間的內(nèi)在關(guān)系（Theintrinsicrelationsbetweendataelements）。根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性，數(shù)據(jù)結(jié)構(gòu)被抽象為四類邏輯結(jié)構(gòu)：線性結(jié)構(gòu)（linearstructure）樹形結(jié)構(gòu)（tree）圖狀結(jié)構(gòu)

（graph）集合結(jié)構(gòu)（set）邏輯結(jié)構(gòu)（LogicalStructure）邏輯結(jié)構(gòu)示意圖線性結(jié)構(gòu)(一對一)樹形結(jié)構(gòu)(一對多)圖狀結(jié)構(gòu)(多對多)集合(松散)邏輯結(jié)構(gòu)（LogicalStructure）獨(dú)立于計(jì)算機(jī)，與是否存儲在計(jì)算機(jī)中無關(guān)；邏輯結(jié)構(gòu)是從具體問題中抽象出來的數(shù)學(xué)模型；Logical_Structure=(D,R)其中：D是數(shù)據(jù)元素的有限集合，R是D上關(guān)系的有限集合。邏輯結(jié)構(gòu)（LogicalStructure）【例1】設(shè)有數(shù)據(jù)結(jié)構(gòu)G=(D,R)，其中：D={A,B,C,D,E}R={<A,B>,<A,E>,<B,C>,<C,D>,<D,B>,<D,A>,<E,C>}畫出邏輯結(jié)構(gòu)示意圖。邏輯結(jié)構(gòu)（LogicalStructure）Python語言內(nèi)置數(shù)據(jù)類型中：線性結(jié)構(gòu)列表類型（list）、元組類型（tuple）和字符串（str）等；集合結(jié)構(gòu)集合（set）和字典（dict）等。邏輯結(jié)構(gòu)（LogicalStructure）存儲結(jié)構(gòu)是指數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)的內(nèi)存中的存儲表示方法（映像方法），存儲內(nèi)容包括：數(shù)據(jù)元素本身；數(shù)據(jù)元素之間的關(guān)系；存儲結(jié)構(gòu)（Storagestructure）數(shù)據(jù)元素映象方法根據(jù)數(shù)據(jù)元素的性質(zhì)選取對應(yīng)的類型進(jìn)行存儲，最終對應(yīng)于若干個(gè)字節(jié)的二進(jìn)制位串。如Python語言中，整數(shù)對象存儲了相應(yīng)的對象頭部和若干字節(jié)的該值的二進(jìn)制補(bǔ)碼。存儲結(jié)構(gòu)（Storagestructure）元素之間關(guān)系的映象方法1．順序存儲結(jié)構(gòu)2．鏈?zhǔn)酱鎯Y(jié)構(gòu)3．索引存儲結(jié)構(gòu)4．哈希存儲結(jié)構(gòu)存儲結(jié)構(gòu)（Storagestructure）如：表示

x,y

的方法：xyxy（a）元素內(nèi)置的順序存儲（b）元素外置的順序存儲1.順序存儲結(jié)構(gòu)Contiguousimplementation元素間的物理位置反映其邏輯關(guān)系存儲結(jié)構(gòu)（Storagestructure）xy2.鏈?zhǔn)酱鎯Y(jié)構(gòu)Linkedimplementation邏輯上相鄰的元素，其物理位置不一定相鄰；元素之間的邏輯關(guān)系由附加的鏈域（指針域）來指示；表示

x,y

的方法：在存儲x對象的同時(shí)附加存儲一個(gè)地址，該地址為y對象的內(nèi)存映像的位置，稱為指向y的指針。存儲結(jié)構(gòu)（Storagestructure）2.鏈?zhǔn)酱鎯Y(jié)構(gòu)Linkedimplementation元素在內(nèi)存中的映像包含：元素值和指針域，這兩個(gè)部分的整體，稱為結(jié)點(diǎn)；每個(gè)結(jié)點(diǎn)的存儲空間是單獨(dú)分配的，因此存儲這些結(jié)點(diǎn)的內(nèi)存空間不一定是連續(xù)的；通過指針域?qū)⒚恳粋€(gè)結(jié)點(diǎn)連接起來，形成鏈?zhǔn)酱鎯Y(jié)構(gòu)。鏈?zhǔn)酱鎯Y(jié)構(gòu)存儲線性表存儲結(jié)構(gòu)（Storagestructure）3.索引存儲結(jié)構(gòu)主數(shù)據(jù)表用順序表存儲元素信息的同時(shí)，再建立附加的索引表。該方法主要用于快速查找數(shù)據(jù)元素。詳見11章。存儲結(jié)構(gòu)（Storagestructure）塊間有序塊內(nèi)可以無序4.哈希存儲結(jié)構(gòu)也稱哈希表，散列表，通常是一個(gè)稀疏順序表，用于存儲集合，元素的存儲位置由關(guān)鍵字值決定。該方法主要用于快速查找數(shù)據(jù)元素。詳見11章。Python中的字典dict和集合set底層就是用哈希存儲結(jié)構(gòu)實(shí)現(xiàn)的。存儲結(jié)構(gòu)（Storagestructure）順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)是兩種最基本、最常用的存儲結(jié)構(gòu)。在實(shí)際應(yīng)用中常將兩者進(jìn)行組合運(yùn)用。同一種邏輯結(jié)構(gòu)可采用不同的存儲方案，得到不同的存儲結(jié)構(gòu)。表示某種邏輯結(jié)構(gòu)時(shí)選擇何種存儲結(jié)構(gòu)，應(yīng)視不同的應(yīng)用場合確定。通常從存儲結(jié)構(gòu)的空間性能、常用基本操作的時(shí)間性能以及算法的簡便性等角度進(jìn)行考慮。存儲結(jié)構(gòu)（Storagestructure）線性表與Python的list的關(guān)系線性表是邏輯結(jié)構(gòu)概念，list是線性表在Python中的一種內(nèi)置存儲實(shí)現(xiàn)方法，線性表可以有其它存儲方式；Python的list中的數(shù)據(jù)元素可以不同構(gòu)。問題討論高級語言中的概念。用于區(qū)分不同性質(zhì)的數(shù)據(jù)并對它們做不同操作。某種特定語言中，確定了對象的數(shù)據(jù)類型，也就確定了該對象的取值范圍、存儲方法和可進(jìn)行的操作。例如Python語言中的整數(shù)數(shù)據(jù)類型用于存儲所有整數(shù)，采用變長結(jié)構(gòu)進(jìn)行存儲，可進(jìn)行的操作有加、減、乘、除、求余數(shù)等。數(shù)據(jù)類型（DataType）Python語言的數(shù)據(jù)類型包括內(nèi)置的數(shù)據(jù)類型、模塊中定義的數(shù)據(jù)類型和用戶自定義的類型。內(nèi)置數(shù)據(jù)類型包括數(shù)值類型、序列類型、集合類型等，數(shù)值類型則包括整數(shù)、浮點(diǎn)數(shù)、復(fù)數(shù)和布爾類型。按照對象值是否可分解，數(shù)據(jù)類型分為原子類型和組合類型。例如：Python數(shù)值對象的值不可再分解，屬于原子類型；而序列類型和集合類型的對象包括了多個(gè)成分，屬于組合類型。數(shù)據(jù)類型（DataType）抽象數(shù)據(jù)類型是指一個(gè)數(shù)學(xué)模型及定義在該模型上的一組操作，簡稱ADT。這個(gè)概念允許我們定義現(xiàn)實(shí)世界中的任何對象，但它去除了數(shù)據(jù)類型概念中關(guān)于具體存儲方法的描述，僅包含兩個(gè)方面：一是對該數(shù)學(xué)模型本身性質(zhì)的描述，二是對該模型的基本操作的描述。ADT定義的兩個(gè)方面對應(yīng)于：數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和對該數(shù)據(jù)結(jié)構(gòu)的操作；因此可以用ADT定義來描述數(shù)據(jù)結(jié)構(gòu)，但注意ADT定義與計(jì)算機(jī)內(nèi)部表示和實(shí)現(xiàn)無關(guān)，因此此時(shí)描述的數(shù)據(jù)結(jié)構(gòu)也不涉及具體的存儲方案。抽象數(shù)據(jù)類型（AbstractDataType）在C++和Java語言中，可以用抽象類來描述抽象數(shù)據(jù)類型，然后再設(shè)計(jì)普通類來實(shí)現(xiàn)抽象類完成對它的表示和操作。在Python語言中，可以通過引入ABC模塊利用抽象基類來描述抽象數(shù)據(jù)類型，ABC是AbstractBaseClass的縮寫。抽象數(shù)據(jù)類型（AbstractDataType）抽象數(shù)據(jù)類型“容器”的定義利用ABC模塊定義一個(gè)抽象基類AbsrtactContainer來表示抽象數(shù)據(jù)類型“容器”。一個(gè)容器類型的對象可以容納多個(gè)元素，并且具有以下操作：返回容器中元素個(gè)數(shù)；判斷容器是否為空；在容器中放入元素item；在容器中刪除元素item；判斷容器中是否包含元素item；清空容器中的所有元素；輸出容器中的所有元素。fromabcimportABCMeta,abstractproperty,abstractmethod

classAbstractContainer(metaclass=ABCMeta):

"""

抽象容器類，metaclass=ABCMeta表示將AbstracContainer類作為ABCMeta的子類

繼承于abc.ABCMeta的類可以使用abstractproperty,abstractmethod修飾器聲明虛屬性與虛方法

"""

@abstractmethod

defsize(self):

"""

返回容器中元素的個(gè)數(shù)

"""

@abstractmethod

defempty(self):

"""

判斷容器是否為空

"""

@abstractmethod

definsert(self,item):

"""

在容器中放入元素item

"""

@abstractmethod

defremove(self,item):

"""

在容器中刪除元素item

"""

@abstractmethod

defcontains(self,item):

"""

判斷容器中是否包含元素item

"""

@abstractmethod

defclear(self):

"""

清空容器中的所有元素

"""

@abstractmethod

defoutput(self):

"""

輸出容器中的所有元素

"""抽象數(shù)據(jù)類型“容器”的定義定義一個(gè)普通類AContainerAContainer繼承抽象基類AbstractContainerAContainer實(shí)現(xiàn)AbstractContainer的各個(gè)方法抽象數(shù)據(jù)類型“容器”的實(shí)現(xiàn)classAContainer(AbstractContainer):

def__init__(self,source=[]):

self.data=source

defsize(self):

returnlen(self.data)

defempty(self):

returnlen(self.data)==0

definsert(self,key):

self.data.append(key)

defcontains(self,x):

returnxinself.data

defremove(self,key):

returnself.data.remove(key)

defclear(self):

self.data.clear()

defoutput(self):

print(self.data)a=AContainer([3,4])

a.insert(5)

a.insert(6)

a.remove(4)

a.output()

a.clear()

a.output()抽象數(shù)據(jù)類型“容器”的實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)、ADT與Python類的關(guān)系用ADT來描述數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)及其操作用Python的抽象類來定義ADT用Python的普通類來實(shí)現(xiàn)ADT，即實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和基本操作當(dāng)然，同一ADT可以有多種不同的實(shí)現(xiàn)方案。數(shù)據(jù)結(jié)構(gòu)通常包括2個(gè)層次：邏輯結(jié)構(gòu)：元素之間的關(guān)系，與計(jì)算機(jī)無關(guān)存儲結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)的存儲，與計(jì)算機(jī)相關(guān)問題數(shù)據(jù)結(jié)構(gòu)課程學(xué)習(xí)的內(nèi)容要在某城市新區(qū)的各小區(qū)之間鋪設(shè)通訊線路,要求連通每個(gè)小區(qū)，并使得總投資最小。請?jiān)O(shè)計(jì)一個(gè)方案。假設(shè)該新區(qū)共有n個(gè)小區(qū)，要連通n個(gè)小區(qū)，至少需要鋪設(shè)多少條線路？n-1如4個(gè)小區(qū)，必須要有3條線路才能連通它們到底選哪幾條線路呢？例：最小代價(jià)鋪設(shè)通訊線路例：最小代價(jià)鋪設(shè)通訊線路a、b、c、d四個(gè)小區(qū)，測算出每兩個(gè)小區(qū)之間鋪設(shè)通訊線路的造價(jià)，并用一個(gè)帶權(quán)圖來表示；圖的頂點(diǎn)表示小區(qū)，頂點(diǎn)之間的邊及權(quán)值表示對應(yīng)小區(qū)間架設(shè)通訊線路時(shí)所需的代價(jià)，如連通a、b小區(qū)的代價(jià)是12萬；這個(gè)最小代價(jià)連通的問題對應(yīng)于圖的最小生成樹的求解問題；整個(gè)問題歸結(jié)為圖的存儲表示和最小生成樹求解的問題。算法實(shí)現(xiàn)/算法分析外部對象（小區(qū)）實(shí)現(xiàn)功能（最小代價(jià)連通）邏輯結(jié)構(gòu)（帶權(quán)圖）基本操作（求解最小生成樹）存儲結(jié)構(gòu)（鄰接矩陣或鄰接表）數(shù)據(jù)抽象問題抽象數(shù)據(jù)表示算法抽象應(yīng)用程序編程調(diào)試與計(jì)算機(jī)無關(guān)數(shù)據(jù)結(jié)構(gòu)課程研究內(nèi)容抽象數(shù)據(jù)類型在于解決兩個(gè)主要問題：根據(jù)實(shí)際問題選擇一種好的數(shù)據(jù)結(jié)構(gòu)；設(shè)計(jì)一個(gè)好的算法，好的算法在很大程度上取決于描述實(shí)際問題的數(shù)據(jù)結(jié)構(gòu)。Programs=Algorithm+DataStructures（程序=算法+數(shù)據(jù)結(jié)構(gòu)）

數(shù)據(jù)結(jié)構(gòu)：問題的數(shù)學(xué)模型，它反映數(shù)據(jù)元素之間關(guān)系。

算法：解決問題的策略、步驟程序設(shè)計(jì)的實(shí)質(zhì)1.確定求解問題的數(shù)學(xué)模型（邏輯結(jié)構(gòu)）；2.確定存儲結(jié)構(gòu)；3.設(shè)計(jì)算法；4.性能分析與改進(jìn)；5.編程、調(diào)試、測試程序設(shè)計(jì)的主要步驟課程內(nèi)容方面過程數(shù)據(jù)表示數(shù)據(jù)處理抽象邏輯結(jié)構(gòu)基本運(yùn)算實(shí)現(xiàn)存儲結(jié)構(gòu)算法評價(jià)不同數(shù)據(jù)結(jié)構(gòu)的比較、選擇和和算法性能分析應(yīng)用使用經(jīng)典數(shù)據(jù)結(jié)構(gòu)編寫程序剖析分析Python的典型數(shù)據(jù)結(jié)構(gòu)AsymptoticTimeComplexity（時(shí)間復(fù)雜度）AsymptoticSpaceComplexity（空間復(fù)雜度）掌握線性表、棧、隊(duì)列、樹、二叉樹、圖等常見的數(shù)據(jù)結(jié)構(gòu)的基本概念、特點(diǎn)、存儲表示、基本操作的實(shí)現(xiàn)及應(yīng)用；掌握算法的設(shè)計(jì)方法，并學(xué)會對算法進(jìn)行性能分析，進(jìn)而設(shè)計(jì)出更高效的算法；掌握計(jì)算機(jī)中最常見的查找、排序等操作的算法原理、實(shí)現(xiàn)方法，并分析比較各算法的性能；采用Python語言描述和實(shí)現(xiàn)各基本數(shù)據(jù)結(jié)構(gòu)的存儲與操作，將Python語言的內(nèi)置數(shù)據(jù)結(jié)構(gòu)作為基本數(shù)據(jù)結(jié)構(gòu)的具體案例進(jìn)行剖析。培養(yǎng)、訓(xùn)練學(xué)生選用合適的數(shù)據(jù)結(jié)構(gòu)，編寫質(zhì)量高、風(fēng)格好的應(yīng)用程序的能力。課程學(xué)習(xí)目標(biāo)算法及特點(diǎn)算法（Algorithm）是對特定問題求解步驟的一種描述（Descriptionoftheparticularstepsoftheprocessofaproblem），是指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作。什么是算法對一個(gè)特定問題，用某種方法描述一個(gè)求解過程，對該問題的每個(gè)實(shí)例，該過程都能給出解，這個(gè)描述就是解決該問題的一個(gè)算法。對一個(gè)特定問題，可能有不同的算法，也可能沒有算法。求任意正實(shí)數(shù)a的平方根的算法（牛頓迭代法）任取一個(gè)非0的初始值x（例如取x=1）；當(dāng)x2

與a之間的差大于誤差，執(zhí)行循環(huán)：x=x-((x2-a)/(2x))；將x作為a的平方根返回；①有窮性，算法必須在執(zhí)行有窮步驟后結(jié)束，而且其中的每一步驟都是有窮的；②可行性，算法的每一條指令所對應(yīng)的操作可以完全機(jī)械地進(jìn)行，并且可在有限的時(shí)間、空間資源下完成；③確定性，算法中的每條指令應(yīng)確切定義、沒有歧義，即對于某個(gè)確定的輸入，算法的執(zhí)行路徑和執(zhí)行結(jié)果都是唯一的；④輸入，算法有明確定義的0個(gè)或多個(gè)輸入；⑤輸出，算法有明確定義的1個(gè)或多個(gè)輸出，表示算法的處理結(jié)果。算法的性質(zhì)算法描述了一個(gè)問題的解決過程，用于人與人之間的交流，交流的內(nèi)容是某一問題的求解過程，主要目的是幫助人們理解和思考相應(yīng)問題的求解思想、方法、所用技術(shù)和過程。在抽象考慮一個(gè)計(jì)算過程，或考慮該求解過程的抽象性質(zhì)時(shí)，常用“算法”作為術(shù)語。在考慮一個(gè)求解過程在某種高級語言下的具體實(shí)現(xiàn)時(shí)，常用“程序”這一術(shù)語。算法和程序

程序是一個(gè)或多個(gè)算法的具體實(shí)現(xiàn)，而算法是程序的抽象、精髓和靈魂；同一算法可用不同的計(jì)算機(jī)語言實(shí)現(xiàn)。程序的性能由其蘊(yùn)含的算法和運(yùn)行的環(huán)境決定。通常語言越高級，程序的效率越差。每一個(gè)程序的背后，都隱藏著一個(gè)或一些算法，正確實(shí)現(xiàn)的程序能解決相關(guān)算法所解決的問題，其（運(yùn)行時(shí)的）動態(tài)性質(zhì)反應(yīng)了相關(guān)算法的特征（是相應(yīng)算法的合理實(shí)現(xiàn)）程序用某種計(jì)算機(jī)能處理的具體編程語言描述，通常會包含一些與具體語言有關(guān)的細(xì)節(jié)結(jié)構(gòu)和描述方式方面的特征。算法具有有窮性，程序不需要具備有窮性。一般的程序都會在有限時(shí)間內(nèi)終止，但有的程序卻可以不在有限時(shí)間內(nèi)終止，如操作系統(tǒng)在正常情況下永遠(yuǎn)都不會終止。算法和程序算法可以用不同的方式描述需要在易讀易理解和嚴(yán)格性之間取得某種平衡用自然語言描述的計(jì)算過程（可能易讀，但可能出現(xiàn)歧義）在自然語言描述中結(jié)合一些數(shù)學(xué)形式的描述（減少歧義）流程圖等框圖采用偽代碼形式，結(jié)合高級語言和自然語言用Python語言，結(jié)合自然語言幫助說明利用Python語言的函數(shù)或類的方法來描述一個(gè)特定算法，采用自頂向下逐步求精的思想進(jìn)行算法設(shè)計(jì)，通常使得每個(gè)函數(shù)或方法完成相對較集中的一個(gè)功能。算法的描述方法任取一個(gè)非0的初始值x（例如取x=1）；當(dāng)x2

與a之間的差大于誤差，執(zhí)行循環(huán)：

x=x-((x2-a)/(2x)),即：x=(x+a/x)/2

將x作為a的平方根返回；求任意實(shí)數(shù)a的平方根的算法（牛頓迭代法）defmy_square_root(a,delta):

x=1

whilemath.fabs(x*x-a)>delta:

x=(x+a/x)/2

returnx實(shí)際應(yīng)用中的算法，具體實(shí)現(xiàn)注定千差萬別。但也有許多算法的設(shè)計(jì)思想有相似之處可以對它們分類，進(jìn)行學(xué)習(xí)和研究設(shè)計(jì)算法的一些通用思想稱為算法設(shè)計(jì)模式。如：暴力枚舉法貪心法分治法回溯法動態(tài)規(guī)劃法分支限界法算法設(shè)計(jì)算法性能分析（1）正確性：要求算法能夠正確地執(zhí)行，并滿足預(yù)先設(shè)定的功能和性能要求，大致分為以下4個(gè)層次：①不含語法錯(cuò)誤。②對于若干組輸入數(shù)據(jù)，能夠得出滿足要求的結(jié)果。③對于精心選擇的典型、苛刻而帶有刁難性的輸入數(shù)據(jù)，能夠得出滿足要求的結(jié)果。④對于一切合法的輸入數(shù)據(jù)，都能夠得出滿足要求的結(jié)果。算法設(shè)計(jì)的目標(biāo)（2）可讀性：算法應(yīng)該容易閱讀，一個(gè)容易閱讀的算法便于人們理解，人們才有可能基于該算法寫出正確的程序。提高算法可讀性的方法主要有兩個(gè):①注釋：一是給算法添加注釋，以方便程序設(shè)計(jì)者和后續(xù)維護(hù)人員閱讀和查錯(cuò)。②命名：要注意對函數(shù)、變量等對象進(jìn)行合理命名。如何評價(jià)一個(gè)算法的好壞（3）健壯性算法應(yīng)具有容錯(cuò)處理的功能，當(dāng)輸入的數(shù)據(jù)不合法或運(yùn)行環(huán)境改變時(shí)，算法都能恰當(dāng)?shù)刈龀龇磻?yīng)或進(jìn)行處理，而不是產(chǎn)生莫名其妙的輸出結(jié)果?？梢酝ㄟ^在算法中增加異常處理語句，對算法進(jìn)行不斷測試和優(yōu)化達(dá)到算法的健壯性。如何評價(jià)一個(gè)算法的好壞（4）高效率算法的效率分為時(shí)間效率和空間效率；時(shí)間效率高：運(yùn)行速度快的算法；空間效率高：算法執(zhí)行過程中占用內(nèi)存空間少；時(shí)間效率和空間效率常常不能同時(shí)兼顧，時(shí)間效率較高的算法可能是犧牲了部分空間效率而獲得。通常更關(guān)注時(shí)間效率。如何評價(jià)一個(gè)算法的好壞（4）高效率在一些應(yīng)用中，為了獲得理想的時(shí)間效率，甚至?xí)档退惴ǖ恼_性要求。天氣預(yù)報(bào)的程序，明天的天氣預(yù)報(bào)計(jì)算至少要在今天下午完成；數(shù)字相機(jī)的人臉識別程序，必須在幾分之一秒完成工作。用戶不會接受更慢的算法。如何評價(jià)一個(gè)算法的好壞選取最優(yōu)的算法對當(dāng)前算法的不足加以改進(jìn)根據(jù)算法分析的結(jié)果進(jìn)一步優(yōu)化數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)算法分析的目的事后統(tǒng)計(jì)法步驟：將算法編制成完整的程序在不同問題規(guī)模、不同輸入案例下執(zhí)行程序統(tǒng)計(jì)程序的絕對運(yùn)行時(shí)間來度量和研究算法的時(shí)間效率。衡量算法時(shí)間效率方法一：事后統(tǒng)計(jì)法利用高級語言中的時(shí)間函數(shù)測量程序運(yùn)行所花的絕對掛鐘時(shí)間，并對時(shí)間數(shù)據(jù)進(jìn)行分析；在Python語言中，可使用time模塊的或perf_counter()或time()等函數(shù)；也可以引入timeit模塊，通過在timeit模塊中創(chuàng)建Timer對象并進(jìn)行相應(yīng)操作，可以測量出指定語句執(zhí)行一定次數(shù)（默認(rèn)100萬次）所花費(fèi)的時(shí)間。具體方法611．其它因素可掩蓋算法本質(zhì)，并不是客觀的算法性能評價(jià)方法。程序的絕對運(yùn)行時(shí)間與軟硬件環(huán)境有關(guān)，受硬件環(huán)境（如處理器性能、內(nèi)存和硬盤容量）以及算法運(yùn)行的軟件環(huán)境（如操作系統(tǒng)，程序設(shè)計(jì)語言）等的影響。2．必須編寫完整程序并運(yùn)行。事后統(tǒng)計(jì)法的缺點(diǎn)程序運(yùn)行時(shí)間相關(guān)因素程序在計(jì)算機(jī)上運(yùn)行所花時(shí)間取決于下列因素：①算法選用何種策略；②問題的規(guī)模；③所使用的程序設(shè)計(jì)語言，就同一個(gè)算法而言，用級別越高的語言實(shí)現(xiàn)，其執(zhí)行的效率越低；④編譯程序所產(chǎn)生的機(jī)器代碼的質(zhì)量；⑤處理器性能、內(nèi)存和硬盤容量等。獨(dú)立于所有軟硬件因素，并不獲得程序執(zhí)行的精準(zhǔn)時(shí)間值；用稱為“時(shí)間復(fù)雜度”的數(shù)量級的量度，反映出隨著問題規(guī)模的增大，算法運(yùn)行時(shí)間的增長趨勢；在算法編制成完整程序前即可衡量出算法的性能。衡量算法時(shí)間效率方法二：事前分析估算將算法運(yùn)行總工作量用算法中所有語句執(zhí)行原操作的次數(shù)之和T(n)表示，T(n)稱為時(shí)間函數(shù)或時(shí)間代價(jià)函數(shù)。原操作是指運(yùn)行時(shí)間是常量時(shí)間的操作；數(shù)值類型數(shù)據(jù)的賦值、所有數(shù)學(xué)運(yùn)算、原子類型數(shù)據(jù)的輸入和輸出等都是原操作；而判斷值x是否在長度為n的列表中的in操作則不是原操作，它包含了若干次值的比較原操作。當(dāng)n

時(shí)，時(shí)間函數(shù)T(n)的數(shù)量級表示稱為漸進(jìn)時(shí)間復(fù)雜度，簡稱時(shí)間復(fù)雜度，記為T(n)=O(f(n))。表示當(dāng)n趨于無窮大時(shí)，算法運(yùn)行時(shí)間由f(n)決定，運(yùn)行時(shí)間的增長率與f(n)的增長率相同。衡量算法時(shí)間效率方法二：事前分析估算例1程序段語句執(zhí)行原操作的次數(shù)foriinrange(0,n):forjinrange(0,n):mc[i][j]=ma[i][j]+mb[i][j]時(shí)間函數(shù)漸進(jìn)時(shí)間復(fù)雜度nn2n2T(n)=2n2+n取時(shí)間函數(shù)的最高次項(xiàng)，得：T(n)=O(n2)解釋在方陣相加算法中，將所有原操作執(zhí)行次數(shù)加起來，得到時(shí)間函數(shù)T(n)=2n2+n，n是方陣的階數(shù)（問題的規(guī)模，規(guī)模因子）。當(dāng)n足夠大時(shí)，對T(n)的值起決定性影響的是第一項(xiàng)2n2，第二項(xiàng)可以忽略不計(jì)，即可以認(rèn)為T(n)的值接近于2n2，進(jìn)而認(rèn)為該算法運(yùn)行時(shí)間的增長率與n2的增長率是相同的，表示為T(n)=O(n2)。這種時(shí)間性能的表示方法稱為算法的漸進(jìn)時(shí)間復(fù)雜度，是一個(gè)數(shù)量級的概念，用大O記號表示，反映出在規(guī)模n趨于無窮大的過程中，算法代價(jià)增長的速度。T(n)=O(n2)，稱為平方階的時(shí)間復(fù)雜度。當(dāng)且僅當(dāng)存在正常數(shù)c和n0，當(dāng)n≥n0，T(n)≤c×f(n)總是成立，則稱該算法的時(shí)間復(fù)雜度為O(f(n))，記為T(n)=O(f(n))。上例中，T(n)=2n2+n

存在正常數(shù)c=3和n0=1，當(dāng)n≥n0時(shí)，T(n)=2n2+n≤2n2+n2≤cn2，總是成立，因此T(n)=O(n2)。以大O表示的時(shí)間復(fù)雜度，是對算法執(zhí)行時(shí)間的一種保守估計(jì)，是算法性能的上界，即對于規(guī)模為n的任意輸入，算法的運(yùn)行時(shí)間都不會超過O(f(n))，即時(shí)間性能不會差于O(f(n))。時(shí)間復(fù)雜度的數(shù)學(xué)定義例2程序段語句執(zhí)行原操作的次數(shù)m=0;foriinrange(1,n+1):forjinrange(i,n+1):m+=1時(shí)間函數(shù)漸進(jìn)時(shí)間復(fù)雜度1nn(n+1)/2n(n+1)/2T(n)=n2+2n+1取時(shí)間函數(shù)的最高次項(xiàng)，得T(n)=O(n2)（1）將所有語句的原操作執(zhí)行次數(shù)之和作為算法的運(yùn)行時(shí)間函數(shù)T(n)。（2）忽略時(shí)間函數(shù)T(n)的低次項(xiàng)部分和最高次項(xiàng)的系數(shù)，只取時(shí)間函數(shù)的最高次項(xiàng)，并輔以大O記號表示。n指的是問題的規(guī)模，如被排序的數(shù)組中元素的個(gè)數(shù)，矩陣的階數(shù)等。時(shí)間復(fù)雜度計(jì)算方法時(shí)間函數(shù)時(shí)間復(fù)雜度(1)n2+1000n(2)3n3+100n2(3)10+3log10n(4)10n+20nlog10n(5)12+n3+2n(6)1000nO(n2)O(n3)O(log10n)O(nlog10n)O(2n)O(n)從算法中選取對于所研究的問題來說是關(guān)鍵操作的語句，以該關(guān)鍵操作語句中重復(fù)執(zhí)行原操作的次數(shù)的數(shù)量級作為算法運(yùn)行時(shí)間效率的量度。關(guān)鍵操作通常是循環(huán)最深層的一句語句，是算法中執(zhí)行原操作的次數(shù)數(shù)量級最高的一句語句，當(dāng)執(zhí)行次數(shù)最高的語句有多句時(shí)，可以選擇任意一句為其關(guān)鍵操作，通常選取算法中完成主要任務(wù)的語句為關(guān)鍵操作。求解時(shí)間復(fù)雜度簡化方法算法時(shí)間復(fù)雜度deff3(lst,i):

lst[i]=lst[i]+1deff4(lst,n):

foriinrange(0,n,2):

lst[i]=lst[i]+1deff5(x,n):

foriinrange(0,n):

forjinrange(0,n):

x=x+1deff6(n):

i=1

whilei<n:

print(i)

i=i*2例3T(n)=O(1)時(shí)間效率與n無關(guān)T(n)=O(n)線性階時(shí)間復(fù)雜度T(n)=O(n2)平方階時(shí)間復(fù)雜度

輸出：12481632n=64時(shí)Python內(nèi)置類型基本操作的性能例4def

f7(n):

data=[]

fori

inrange(n):

data.insert(0,i)

returndata

deff8(n):

data=[]

foriinrange(n):

data.insert(i,i)

returndataT(n)=O(n)線性階時(shí)間復(fù)雜度T(n)=O(n2)平方階時(shí)間復(fù)雜度Python的很多基本操作不是原操作！（1）構(gòu)造一個(gè)包含n個(gè)元素的結(jié)構(gòu)（2）list操作的效率，如元素訪問和元素賦值，加入刪除元素等？復(fù)制和切片操作？（3）字典dict操作的效率加入新的關(guān)鍵碼-值對，關(guān)鍵碼查找等程序里經(jīng)常用到這些操作，它們的效率對程序效率有重大影響有些操作效率更高，應(yīng)該優(yōu)先選用Python對象常見操作時(shí)間復(fù)雜度O(1)O(n)O(1)Python列表常見操作時(shí)間復(fù)雜度基本操作

說明平均時(shí)間復(fù)雜度copy復(fù)制append尾部插入O(1)poplast刪除最后一個(gè)元素O(1)popintermediate刪除非尾部位置的元素O(k)insert插入O(n)getItem元素值的讀取O(1)setItem元素值的寫入O(1)deleteItem刪除值為item的元素O(n)setslice設(shè)置切片(切片長度為k)O(n+k)getslice切片k個(gè)元素O(k)Sort排序O(nlogn)multiply乘kO(nk)xins判斷x是否在表s中O(n)min(s),max(s)查找表s的最小、最大值O(n)getlength求表長/moin/TimeComplexityO(n)O(1)O(1)O(k)O(n)O(1)O(1)O(n)O(n+k)O(k)O(nlogn)O(nk)O(n)O(n)O(1)基本操作說明平均時(shí)間復(fù)雜度copy復(fù)制O(n)getitem讀取元素O(1)setitem寫入元素O(1)deleteitem刪除元素O(1)iteration遍歷O(n)Python字典常見操作時(shí)間復(fù)雜度O(n)O(1)O(1)O(1)O(n)用Python等高級語言編程，存在一些“效率陷阱”有些看起來很簡短的程序，實(shí)際上需要很高的時(shí)間代價(jià)；這樣的缺陷會損害軟件的可用性，甚至葬送一個(gè)軟件；為了有效使用Python語言中的各種類型，應(yīng)深入了解各內(nèi)置類型的具體實(shí)現(xiàn)方案及其常見操作的性能。效率陷阱常見的時(shí)間復(fù)雜度

常見的時(shí)間復(fù)雜度例：設(shè)解決某具體問題的關(guān)鍵操作每秒做10000次，問題規(guī)模n為100O(n)的算法，所需時(shí)間可忽略不計(jì)（1/100秒）O(n3)的算法，所需時(shí)間是分鐘的量級O(2n)的算法，所需時(shí)間是4.0*1018年的量級。（迄今為之的宇宙壽命估計(jì)為1010年的量級）算法的時(shí)間復(fù)雜度比較時(shí)間復(fù)雜度排序O(1) 常數(shù)階O(log2n) 對數(shù)階O(n) 線性階O(nlog2n)線性對數(shù)階O(n2) 平方階O(n3)

立方階O(2n) 指數(shù)階從上到下從好到壞復(fù)雜度從低到高時(shí)間效率從高到低時(shí)間復(fù)雜度計(jì)算原則并列程序段----加法原則當(dāng)算法由并列的若干程序段組成時(shí)，整個(gè)算法的時(shí)間復(fù)雜度可以取所有程序段中的時(shí)間復(fù)雜度之和，稱為加法原則。T(n)=T1(n)+T2(n)=O(T1(n))+O(T2(n))=O(max(T1(n),T2(n)))由于忽略常量因子，加法等價(jià)于求最大值。加法原則嵌套程序段----乘法原則如果算法由若干嵌套循環(huán)的程序段組成時(shí)，整個(gè)算法的時(shí)間復(fù)雜度取所有程序段中的時(shí)間復(fù)雜度的乘積，稱為乘法原則。如果算法中循環(huán)執(zhí)行T1(n)次，每次循環(huán)用T2(n)時(shí)間，則

T(n)=T1(n)×T2(n)

=O(T1(n))×O(T2(n))=O(T1(n)×T2(n))乘法原則舉例1defmult(m1,m2):2n=len(m1)

#3m=[[0foriinrange(n)]forjinrange(n)]#4foriinrange(n):

#5forjinrange(n): #6x=0 #7forkinrange(n): #8x+=m1[i][k]*m2[k][j]#9m[i][j]=x #10returnm

#

（1）時(shí)間復(fù)雜度與輸入實(shí)例的初始排列、輸入?yún)?shù)有關(guān)。例：在一個(gè)長度為n的列表中查找一個(gè)值為x的元素。其它情況deffind(lst,x):

n=len(lst)

foriinrange(n):

iflst[i]==x:

returni

return-1最好情況；最壞情況時(shí)間復(fù)雜度，它給出一種保證：算法在該時(shí)間期限內(nèi)一定能完成工作；平均情況下的時(shí)間復(fù)雜度是根據(jù)當(dāng)前輸入數(shù)據(jù)的不同分布情況，按照每種情況發(fā)生的概率進(jìn)行運(yùn)算而得到的平均時(shí)間效率，常假設(shè)每種情況的發(fā)生概率相同；通常計(jì)算最壞情況和平均情況。平均和最壞情況時(shí)間復(fù)雜度（2）攤銷時(shí)間復(fù)雜度有的算法會在觸發(fā)某個(gè)條件時(shí)做額外的工作，此時(shí)，可以根據(jù)這個(gè)條件發(fā)生的概率，對整個(gè)算法進(jìn)行性能評估，此時(shí)得到的時(shí)間復(fù)雜度稱為攤銷時(shí)間復(fù)雜度。其它情況（3）多個(gè)問題規(guī)模一個(gè)特定算法的運(yùn)行時(shí)間依賴于問題的規(guī)模，但有的時(shí)候，問題的規(guī)模不止一個(gè)。比如，對兩個(gè)長度分別為n和k的數(shù)組進(jìn)行操作，問題的規(guī)模就有2個(gè)，這時(shí)時(shí)間復(fù)雜度是關(guān)于n和k的函數(shù)。a_list=[0,1,2,3,4,5,6,7,8,9]

a_list[1:3]=['a','b','c','d','e']執(zhí)行上述語句后a_list的結(jié)果是什么？分析第2行語句實(shí)際完成了哪些工作？（設(shè)原表長為n，切片[i:j]的對應(yīng)長度為m，即m=j-i，切片替換部分長度為k）其它情況[0,'a','b','c','d','e',3,4,5,6,7,8,9]n=10,i=1,j=3,m=2,k=5，由于k>m，所以將n-1號開始一直到j(luò)號位置的元素依次后移k-m個(gè)位置，即從9開始到3的全部元素后移3個(gè)位置，再將,‘a(chǎn)’,‘b’,‘c’,‘d’,‘e’,依次賦給a_list[1]---a_list[5]。

defprime(n):

foriinrange(2,int(math.sqrt(n))+1):

ifn%i==0:

returnFalse

returnTrue其它情況definsertion_sort(lst):

foriinrange(1,len(lst)):

j=i-1

current=lst[i]

whilej>=0:

iflst[j]>current:

lst[j+1]=lst[j]

else:

break

j-=1

lst[j+1]=current若算法中不存在循環(huán)----O(1)?如算法中的每一句語句都為原操作，則算法時(shí)間復(fù)雜度為常量階；若算法中僅存在一重循環(huán)---O(n)?循環(huán)體內(nèi)僅包含原操作決定算法時(shí)間復(fù)雜度的是該循環(huán)中關(guān)鍵語句的原操作執(zhí)行次數(shù)；如循環(huán)變量以常數(shù)遞增或遞減，。。。若算法中存在m重循環(huán)---O(nm)?決定算法時(shí)間復(fù)雜度的是循環(huán)嵌套層數(shù)最深的關(guān)鍵語句的原操作的執(zhí)行次數(shù)。問題？算法的空間復(fù)雜度與算法的時(shí)間復(fù)雜度類似，算法的空間復(fù)雜度也認(rèn)為是問題規(guī)模n的函數(shù)，并以數(shù)量級的形式給出，記作S(n)=O(g(n))程序在計(jì)算機(jī)運(yùn)行時(shí)所占用的存儲空間包括以下部分：輸入數(shù)據(jù)所占用的存儲空間程序本身所占用的