數(shù)據(jù)結(jié)構(gòu)與算法python描述

數(shù)據(jù)結(jié)構(gòu)與算法Python描述2知識目標什么是算法設(shè)計？算法的時間和空間復雜性計算和數(shù)據(jù)表示數(shù)據(jù)結(jié)構(gòu)01能力目標了解何為算法設(shè)計算法的時間和空間復雜性掌握計算和數(shù)據(jù)表示了解數(shù)據(jù)結(jié)構(gòu)02學習目標3目錄01什么是算法設(shè)計？02算法的時間和空間復雜性03計算和數(shù)據(jù)表示04數(shù)據(jù)結(jié)構(gòu)4算法設(shè)計通過分析構(gòu)造出問題的求解模型后，下步考慮求解算法（的設(shè)計）算法設(shè)計研究求解問題的嚴格方法設(shè)計好的算法為編程實現(xiàn)提供了堅實的基礎(chǔ)解決本問題（圖著色問題）有許多方法不同方法有不同的性質(zhì)，需要考慮5算法設(shè)計方法1，通過窮舉選出最優(yōu)設(shè)法逐個枚舉出所有可能的合法分組，在枚舉過程中，記錄遇到的最小分組個數(shù)和

對應(yīng)的分組情況這一過程一定能找到一個“最優(yōu)”解（分組數(shù)最少的解）缺點：可能組合數(shù)太多，逐個枚舉需要指數(shù)時間（算法的效率低）如果不同方向的集合比較大，求解時間可能長得無法忍受交通路口的支路不多（超過4的情況不多見），可以考慮這一算法6算法設(shè)計方法2.“貪心法”這是一類典型的算法設(shè)計思路（算法的設(shè)計模式），基本想法是根據(jù)當時掌握的信息，盡可能地向得到解的方向推進通常不能找到最優(yōu)解，但能找到“可接受的”解7算法設(shè)計算法梗概（偽代碼）:設(shè)法表示圖

G集合

verts

保存

G

中所有結(jié)點設(shè)置集合

groups

=

空集while

存在未著色結(jié)點

:選一種新顏色#

記錄圖中的結(jié)點連接關(guān)系#

建立初始狀態(tài)#

記錄得到的分組，元素是集合#

用貪心法反復找新分組在未著色結(jié)點中給盡量多無互連邊的點著色（構(gòu)建一個分組）記錄新著色的結(jié)點組#算法結(jié)束時集合groups里記錄著一種分組方式#算法細節(jié)還需要進一步考慮8算法設(shè)計采用貪心法，按結(jié)點排列順序試探（演示）：9算法設(shè)計貪心法應(yīng)用于圖1.2，得到的分組：綠色：AB,AC,AD,BA,DC,ED藍色：BC,

BD,

EA紅色：DA,

DB白色：EB,

EC10算法(Algorithm)算法是問題求解過程的精確描述，具有如下性質(zhì)：有窮性（描述的有窮性）：由有限條“指令”/“語句”構(gòu)成能行性：指令（語句）含義簡單明確，其過程可以完全機械地進行確定性：作用于所求解問題的給定輸入（要處理的問題實例的某種描述），將產(chǎn)生出唯一的確定的動作序列確定性算法11算法(Algorithm)也可以考慮更廣泛的概念，如非確定性算法終止性（行為的有窮性）：產(chǎn)生的動作序列有窮，它或終止并給出問題的解；或終止并指出對給定的輸入本問題無解也存在不要求終止的計算描述，或稱為“過程(pocedure)”輸入/輸出：有確定的輸入和輸出12算法的時間和空間復雜性考慮時空代價時，有些因素的準確值意義不大，例如：時間或空間的基本單位算法描述和實現(xiàn)的細節(jié)差異

人們最關(guān)注的是算法代價的關(guān)鍵情況和趨勢，排除各方面具體細節(jié)從這種看法出發(fā)，人們定義了算法“復雜性”的概念同樣，可以考慮時間和空間復雜性13算法的時間和空間復雜性在理論上考慮復雜性時，通常忽略常量因子例如，代價為3n2和100n2的算法，看作復雜性相同的算法如果算法改進只是減小常量因子，從理論上看其復雜性沒變，但在實際中可能有意義例：3天算出明天的天氣預報，與半天算出明天的天氣預報14遞歸算法的復雜性對比較規(guī)范的遞歸算法，有清晰的理論分析方法前面行列式求值的遞歸算法的情況更復雜一些設(shè)一個遞歸求解算法，將規(guī)模為n的問題實例歸結(jié)到a個規(guī)模為n/b的子問題，每次遞歸時還需要做O(nk)的其他工作，那么15遞歸算法的復雜性求解這一遞歸方程，可以得到下面結(jié)果：當 時，當 時，當 時，注意：這里的a、b和k是常量，可以覆蓋大部分典型情況對前面行列式求值的示例，上面的解無效（上面公式中a和b為常量）16計算和數(shù)據(jù)表示信息表示A 信息表示B程序計算機用計算機解決問題，可以認為是實現(xiàn)某種信息表示形式的轉(zhuǎn)換17計算和數(shù)據(jù)表示如果：D“信息表示A”表達了需要求解的某個問題“信息表示B”表達了相應(yīng)的求解結(jié)果

可以認為：這個程序完成該問題的求解為處理與問題有關(guān)的信息，必須用某種方式表示它，并將相應(yīng)表示存入計算機。這種信息表示就稱為（計算機處理的）數(shù)據(jù)為有效使用，必須以某種方式把程序使用的數(shù)據(jù)組織好。程序越復雜，需要處理的數(shù)據(jù)情況越復雜，數(shù)據(jù)的良好組織就越重要18數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)（Data）：計算機程序能處理的符號形式的總和信息（information）是一個含義更廣泛的概念

一種說法：數(shù)據(jù)是編碼的信息（信息的編碼表示）數(shù)據(jù)元素（DataElement）數(shù)據(jù)的基本單位，在程序中通常作為一個整體考慮和處理19數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)（DataStructures）一組數(shù)據(jù)元素（結(jié)點）按照一定方式構(gòu)成的復合數(shù)據(jù)形式以及作用于這些元素或者結(jié)構(gòu)上的一些函數(shù)或操作本課程將討論一批典型的常用數(shù)據(jù)結(jié)構(gòu)：表/堆棧/隊列/鏈接表/字符串/樹/二叉樹/字典/集合/圖幫助大家理解復雜數(shù)據(jù)的表示和處理技術(shù)，各種結(jié)構(gòu)的性質(zhì)（支持哪些操作，操作的代價等），進一步理解計算的本質(zhì)20數(shù)據(jù)結(jié)構(gòu)一種數(shù)據(jù)結(jié)構(gòu)是采用一套特定方式建立起來的一種數(shù)據(jù)組織結(jié)構(gòu)（以數(shù)據(jù)元素為出發(fā)點），其特征包括幾個方面（層次）：邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間有某種特定的邏輯關(guān)系。這是元素之間的抽象關(guān)系，與實現(xiàn)無關(guān)。抽象看，一個數(shù)據(jù)結(jié)構(gòu)是一個二元組B=(E,R

)E是一些種類的數(shù)據(jù)的集合，B的元素取自集合E元素之間有關(guān)系R，不同數(shù)據(jù)結(jié)構(gòu)的元素之間的關(guān)系不同21數(shù)據(jù)結(jié)構(gòu)物理結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲器中的映射（或表示），又稱存儲結(jié)構(gòu)，或數(shù)據(jù)結(jié)構(gòu)的存儲表示行為特征：作用于數(shù)據(jù)結(jié)構(gòu)上的各種運算。例如檢索元素、插入元素、刪除元素等一般性操作，還可能有一些特殊操作具體實現(xiàn)問題：在編程語言里實現(xiàn)數(shù)據(jù)結(jié)構(gòu)的具體方式和技術(shù)對Python，還需理解其重要內(nèi)置數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)和性質(zhì)22Python數(shù)據(jù)結(jié)構(gòu)典型的數(shù)據(jù)元素是不可進一步分割的原子，如整數(shù)、浮點數(shù)、布爾值每種編程語言都提供了一組基本數(shù)據(jù)類型，如整數(shù)，浮點數(shù)，邏輯類型等。這些類型的數(shù)據(jù)元都應(yīng)看作數(shù)據(jù)元素語言還為每個基本類型提供了一批操作23Python數(shù)據(jù)結(jié)構(gòu)常規(guī)語言通常提供幾種基本的數(shù)據(jù)組織機制用于把一組簡單（或復雜）的數(shù)據(jù)元素組織為一個整體，滿足程序中管理、操作和傳輸?shù)男枰行┱Z言，如C語言，只提供了幾個基本類型和兩三種數(shù)據(jù)構(gòu)造機制，所有復雜的數(shù)據(jù)結(jié)構(gòu)都需要自己定義另一些語言（包括Python）本身就提供了一批高級的數(shù)據(jù)類型，其中一些實際上是最有用的數(shù)據(jù)結(jié)構(gòu)。如Python的list等24Python數(shù)據(jù)結(jié)構(gòu)上學期介紹了Python的一些標準數(shù)據(jù)類型，其中一些實際上就是非常有用的數(shù)據(jù)正文序列類型str序列類型list和tuple集合類型set和frozenset映射類型dict25Python數(shù)據(jù)結(jié)構(gòu)本課程中還會反復使用它們標準庫還提供了另一些數(shù)據(jù)結(jié)構(gòu)定義，如deque等下面簡單羅列一些情況，請大家自己回憶和復習本課程后面討論中在這方面要強調(diào)的重點是：剖析這些數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)和性質(zhì)幫助理解在寫程序時應(yīng)該如何使用它們，以及為什么26Python數(shù)據(jù)結(jié)構(gòu)（簡單回顧）字符串，類型名str，不變（immutable）正文序列類型對象：字符的有窮序列訪問操作：求長度，取成員，取子串（切片），查找子串，判斷成員字符類型，等等基于已有字符串構(gòu)造新串：改變大小寫，拼接，格式化（變換格式），子串替換，切分，等等。都是構(gòu)造新串27Python數(shù)據(jù)結(jié)構(gòu)（簡單回顧）元組，類型名tuple，不變序列類型對象：任意