版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
數(shù)據(jù)結(jié)構(gòu)與算法Python描述2知識(shí)目標(biāo)什么是算法設(shè)計(jì)?算法的時(shí)間和空間復(fù)雜性計(jì)算和數(shù)據(jù)表示數(shù)據(jù)結(jié)構(gòu)01能力目標(biāo)了解何為算法設(shè)計(jì)算法的時(shí)間和空間復(fù)雜性掌握計(jì)算和數(shù)據(jù)表示了解數(shù)據(jù)結(jié)構(gòu)02學(xué)習(xí)目標(biāo)3目錄01什么是算法設(shè)計(jì)?02算法的時(shí)間和空間復(fù)雜性03計(jì)算和數(shù)據(jù)表示04數(shù)據(jù)結(jié)構(gòu)4算法設(shè)計(jì)通過分析構(gòu)造出問題的求解模型后,下步考慮求解算法(的設(shè)計(jì))算法設(shè)計(jì)研究求解問題的嚴(yán)格方法設(shè)計(jì)好的算法為編程實(shí)現(xiàn)提供了堅(jiān)實(shí)的基礎(chǔ)解決本問題(圖著色問題)有許多方法不同方法有不同的性質(zhì),需要考慮5算法設(shè)計(jì)方法1,通過窮舉選出最優(yōu)設(shè)法逐個(gè)枚舉出所有可能的合法分組,在枚舉過程中,記錄遇到的最小分組個(gè)數(shù)和
對(duì)應(yīng)的分組情況這一過程一定能找到一個(gè)“最優(yōu)”解(分組數(shù)最少的解)缺點(diǎn):可能組合數(shù)太多,逐個(gè)枚舉需要指數(shù)時(shí)間(算法的效率低)如果不同方向的集合比較大,求解時(shí)間可能長得無法忍受交通路口的支路不多(超過4的情況不多見),可以考慮這一算法6算法設(shè)計(jì)方法2.“貪心法”這是一類典型的算法設(shè)計(jì)思路(算法的設(shè)計(jì)模式),基本想法是根據(jù)當(dāng)時(shí)掌握的信息,盡可能地向得到解的方向推進(jìn)通常不能找到最優(yōu)解,但能找到“可接受的”解7算法設(shè)計(jì)算法梗概(偽代碼):設(shè)法表示圖
G集合
verts
保存
G
中所有結(jié)點(diǎn)設(shè)置集合
groups
=
空集while
存在未著色結(jié)點(diǎn)
:選一種新顏色#
記錄圖中的結(jié)點(diǎn)連接關(guān)系#
建立初始狀態(tài)#
記錄得到的分組,元素是集合#
用貪心法反復(fù)找新分組在未著色結(jié)點(diǎn)中給盡量多無互連邊的點(diǎn)著色(構(gòu)建一個(gè)分組)記錄新著色的結(jié)點(diǎn)組#算法結(jié)束時(shí)集合groups里記錄著一種分組方式#算法細(xì)節(jié)還需要進(jìn)一步考慮8算法設(shè)計(jì)采用貪心法,按結(jié)點(diǎn)排列順序試探(演示):9算法設(shè)計(jì)貪心法應(yīng)用于圖1.2,得到的分組:綠色:AB,AC,AD,BA,DC,ED藍(lán)色:BC,
BD,
EA紅色:DA,
DB白色:EB,
EC10算法(Algorithm)算法是問題求解過程的精確描述,具有如下性質(zhì):有窮性(描述的有窮性):由有限條“指令”/“語句”構(gòu)成能行性:指令(語句)含義簡單明確,其過程可以完全機(jī)械地進(jìn)行確定性:作用于所求解問題的給定輸入(要處理的問題實(shí)例的某種描述),將產(chǎn)生出唯一的確定的動(dòng)作序列確定性算法11算法(Algorithm)也可以考慮更廣泛的概念,如非確定性算法終止性(行為的有窮性):產(chǎn)生的動(dòng)作序列有窮,它或終止并給出問題的解;或終止并指出對(duì)給定的輸入本問題無解也存在不要求終止的計(jì)算描述,或稱為“過程(pocedure)”輸入/輸出:有確定的輸入和輸出12算法的時(shí)間和空間復(fù)雜性考慮時(shí)空代價(jià)時(shí),有些因素的準(zhǔn)確值意義不大,例如:時(shí)間或空間的基本單位算法描述和實(shí)現(xiàn)的細(xì)節(jié)差異
人們最關(guān)注的是算法代價(jià)的關(guān)鍵情況和趨勢,排除各方面具體細(xì)節(jié)從這種看法出發(fā),人們定義了算法“復(fù)雜性”的概念同樣,可以考慮時(shí)間和空間復(fù)雜性13算法的時(shí)間和空間復(fù)雜性在理論上考慮復(fù)雜性時(shí),通常忽略常量因子例如,代價(jià)為3n2和100n2的算法,看作復(fù)雜性相同的算法如果算法改進(jìn)只是減小常量因子,從理論上看其復(fù)雜性沒變,但在實(shí)際中可能有意義例:3天算出明天的天氣預(yù)報(bào),與半天算出明天的天氣預(yù)報(bào)14遞歸算法的復(fù)雜性對(duì)比較規(guī)范的遞歸算法,有清晰的理論分析方法前面行列式求值的遞歸算法的情況更復(fù)雜一些設(shè)一個(gè)遞歸求解算法,將規(guī)模為n的問題實(shí)例歸結(jié)到a個(gè)規(guī)模為n/b的子問題,每次遞歸時(shí)還需要做O(nk)的其他工作,那么15遞歸算法的復(fù)雜性求解這一遞歸方程,可以得到下面結(jié)果:當(dāng) 時(shí),當(dāng) 時(shí),當(dāng) 時(shí),注意:這里的a、b和k是常量,可以覆蓋大部分典型情況對(duì)前面行列式求值的示例,上面的解無效(上面公式中a和b為常量)16計(jì)算和數(shù)據(jù)表示信息表示A 信息表示B程序計(jì)算機(jī)用計(jì)算機(jī)解決問題,可以認(rèn)為是實(shí)現(xiàn)某種信息表示形式的轉(zhuǎn)換17計(jì)算和數(shù)據(jù)表示如果:D“信息表示A”表達(dá)了需要求解的某個(gè)問題“信息表示B”表達(dá)了相應(yīng)的求解結(jié)果
可以認(rèn)為:這個(gè)程序完成該問題的求解為處理與問題有關(guān)的信息,必須用某種方式表示它,并將相應(yīng)表示存入計(jì)算機(jī)。這種信息表示就稱為(計(jì)算機(jī)處理的)數(shù)據(jù)為有效使用,必須以某種方式把程序使用的數(shù)據(jù)組織好。程序越復(fù)雜,需要處理的數(shù)據(jù)情況越復(fù)雜,數(shù)據(jù)的良好組織就越重要18數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)(Data):計(jì)算機(jī)程序能處理的符號(hào)形式的總和信息(information)是一個(gè)含義更廣泛的概念
一種說法:數(shù)據(jù)是編碼的信息(信息的編碼表示)數(shù)據(jù)元素(DataElement)數(shù)據(jù)的基本單位,在程序中通常作為一個(gè)整體考慮和處理19數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(DataStructures)一組數(shù)據(jù)元素(結(jié)點(diǎn))按照一定方式構(gòu)成的復(fù)合數(shù)據(jù)形式以及作用于這些元素或者結(jié)構(gòu)上的一些函數(shù)或操作本課程將討論一批典型的常用數(shù)據(jù)結(jié)構(gòu):表/堆棧/隊(duì)列/鏈接表/字符串/樹/二叉樹/字典/集合/圖幫助大家理解復(fù)雜數(shù)據(jù)的表示和處理技術(shù),各種結(jié)構(gòu)的性質(zhì)(支持哪些操作,操作的代價(jià)等),進(jìn)一步理解計(jì)算的本質(zhì)20數(shù)據(jù)結(jié)構(gòu)一種數(shù)據(jù)結(jié)構(gòu)是采用一套特定方式建立起來的一種數(shù)據(jù)組織結(jié)構(gòu)(以數(shù)據(jù)元素為出發(fā)點(diǎn)),其特征包括幾個(gè)方面(層次):邏輯結(jié)構(gòu):數(shù)據(jù)元素之間有某種特定的邏輯關(guān)系。這是元素之間的抽象關(guān)系,與實(shí)現(xiàn)無關(guān)。抽象看,一個(gè)數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組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)在計(jì)算機(jī)存儲(chǔ)器中的映射(或表示),又稱存儲(chǔ)結(jié)構(gòu),或數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)表示行為特征:作用于數(shù)據(jù)結(jié)構(gòu)上的各種運(yùn)算。例如檢索元素、插入元素、刪除元素等一般性操作,還可能有一些特殊操作具體實(shí)現(xiàn)問題:在編程語言里實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)的具體方式和技術(shù)對(duì)Python,還需理解其重要內(nèi)置數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)和性質(zhì)22Python數(shù)據(jù)結(jié)構(gòu)典型的數(shù)據(jù)元素是不可進(jìn)一步分割的原子,如整數(shù)、浮點(diǎn)數(shù)、布爾值每種編程語言都提供了一組基本數(shù)據(jù)類型,如整數(shù),浮點(diǎn)數(shù),邏輯類型等。這些類型的數(shù)據(jù)元都應(yīng)看作數(shù)據(jù)元素語言還為每個(gè)基本類型提供了一批操作23Python數(shù)據(jù)結(jié)構(gòu)常規(guī)語言通常提供幾種基本的數(shù)據(jù)組織機(jī)制用于把一組簡單(或復(fù)雜)的數(shù)據(jù)元素組織為一個(gè)整體,滿足程序中管理、操作和傳輸?shù)男枰行┱Z言,如C語言,只提供了幾個(gè)基本類型和兩三種數(shù)據(jù)構(gòu)造機(jī)制,所有復(fù)雜的數(shù)據(jù)結(jié)構(gòu)都需要自己定義另一些語言(包括Python)本身就提供了一批高級(jí)的數(shù)據(jù)類型,其中一些實(shí)際上是最有用的數(shù)據(jù)結(jié)構(gòu)。如Python的list等24Python數(shù)據(jù)結(jié)構(gòu)上學(xué)期介紹了Python的一些標(biāo)準(zhǔn)數(shù)據(jù)類型,其中一些實(shí)際上就是非常有用的數(shù)據(jù)正文序列類型str序列類型list和tuple集合類型set和frozenset映射類型dict25Python數(shù)據(jù)結(jié)構(gòu)本課程中還會(huì)反復(fù)使用它們標(biāo)準(zhǔn)庫還提供了另一些數(shù)據(jù)結(jié)構(gòu)定義,如deque等下面簡單羅列一些情況,請(qǐng)大家自己回憶和復(fù)習(xí)本課程后面討論中在這方面要強(qiáng)調(diào)的重點(diǎn)是:剖析這些數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)和性質(zhì)幫助理解在寫程序時(shí)應(yīng)該如何使用它們,以及為什么26Python數(shù)據(jù)結(jié)構(gòu)(簡單回顧)字符串,類型名str,不變(immutable)正文序列類型對(duì)象:字符的有窮序列訪問操作:求長度,取成員,取子串(切片),查找子串,判斷成員字符類型,等等基于已有字符串構(gòu)造新串:改變大小寫,拼接,格式化(變換格式),子串替換,切分,等等。都是構(gòu)造新串27Python數(shù)據(jù)結(jié)構(gòu)(簡單回顧)元組,類型名tuple,不變序列類型對(duì)象:任意
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025年度養(yǎng)老院車庫租賃與養(yǎng)老服務(wù)合同4篇
- 2025年度出租車公司車輛安全檢查合同6篇
- 2024年船舶加油與貨物運(yùn)輸合同
- 2025年度生態(tài)魚塘租賃及管理服務(wù)合同4篇
- 2025年度石油鉆井設(shè)備租賃與技術(shù)服務(wù)合同4篇
- 2024版洗碗工勞動(dòng)合同違約金
- 2024科技公司與科研機(jī)構(gòu)之間的聯(lián)合研發(fā)合同
- 2024造價(jià)咨詢服務(wù)合作協(xié)議-裝配式建筑版3篇
- 2025年度智慧城市建設(shè)項(xiàng)目車位使用權(quán)租賃合同4篇
- 2025年度時(shí)尚餐廳裝修設(shè)計(jì)及設(shè)備采購合同3篇
- 勞務(wù)投標(biāo)技術(shù)標(biāo)
- 研發(fā)管理咨詢項(xiàng)目建議書
- 濕瘡的中醫(yī)護(hù)理常規(guī)課件
- 轉(zhuǎn)錢委托書授權(quán)書范本
- 一種配網(wǎng)高空作業(yè)智能安全帶及預(yù)警系統(tǒng)的制作方法
- 某墓園物業(yè)管理日常管護(hù)投標(biāo)方案
- 蘇教版六年級(jí)數(shù)學(xué)上冊(cè)集體備課記載表
- NUDD新獨(dú)難異 失效模式預(yù)防檢查表
- 內(nèi)蒙古匯能煤電集團(tuán)有限公司長灘露天煤礦礦山地質(zhì)環(huán)境保護(hù)與土地復(fù)墾方案
- 22S702 室外排水設(shè)施設(shè)計(jì)與施工-鋼筋混凝土化糞池
- 2013日產(chǎn)天籟全電路圖維修手冊(cè)45車身控制系統(tǒng)
評(píng)論
0/150
提交評(píng)論