數據結構與算法python描述

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

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

G集合

verts

保存

G

中所有結點設置集合

groups

=

空集while

存在未著色結點

:選一種新顏色#

記錄圖中的結點連接關系#

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

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

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

BD,

EA紅色：DA,

DB白色：EB,

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

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

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

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

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