數(shù)據(jù)結(jié)構(gòu)第一章(完整版)
【正文】 it位數(shù)，例如：兩個(gè)整型數(shù)據(jù)的乘法 3. 有時(shí)，輸入規(guī)模用兩個(gè)數(shù)表示，例如輸入是一個(gè) 圖 所以，解決問(wèn)題之前先弄清 問(wèn)題的輸入規(guī)模 后面均將輸入規(guī)模抽象成 n，算法的運(yùn)行時(shí)間表示成 T(n),n的函數(shù) 算法復(fù)雜度分析 ? 最好運(yùn)行時(shí)間 同樣的輸入規(guī)模，不同的數(shù)據(jù)分布情況下，最快情況的運(yùn)行時(shí)間。 操作結(jié)果：用 sum返回兩個(gè)復(fù)數(shù) z1, z2 的和值。 GetReal( Z, amp。 STUDENT stu, *pstu。主 講：張偉 單 位：信息學(xué)院通信與信息系統(tǒng)研究所 日 期： 2022年 9月 東北大學(xué) 數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法 學(xué)習(xí)內(nèi)容 數(shù)據(jù)結(jié)構(gòu)和算法概述（ 2學(xué)時(shí)） 基本數(shù)據(jù)結(jié)構(gòu)（ 4學(xué)時(shí)） 遞歸與樹(shù)（ 4學(xué)時(shí)） 圖（ 8學(xué)時(shí)） 查找（ 4學(xué)時(shí)） 排序（ 4學(xué)時(shí)） 算法設(shè)計(jì)策略（ 6學(xué)時(shí)） 使用教材 教材 ： 《 數(shù)據(jù)結(jié)構(gòu)（ C語(yǔ)言版） 》 ， 嚴(yán)蔚敏 吳偉民編著，清華大學(xué)出版社 參考書 ： 《 計(jì)算機(jī)算法設(shè)計(jì)與分析 》 ，王曉東編著， 電子工業(yè)出版社 聯(lián)系方式 ? Email : ? Address：礦電樓 102 ? Office Tel： 83683048 第一章 數(shù)據(jù)結(jié)構(gòu)和算法概述 本章內(nèi)容 問(wèn)題的求解 數(shù)據(jù)結(jié)構(gòu)及抽象數(shù)據(jù)類型 算法的概念和特性 算法的效率度量 漸進(jìn)表示法和漸進(jìn)記號(hào) 問(wèn)題求解 ? 階段和步驟 ? 獲取需求（問(wèn)題），以保證解決的問(wèn)題正是需要的（ solve the right problem）； ? 分析問(wèn)題，將其分解為粒度更小的部分； ? 針對(duì)問(wèn)題（子問(wèn)題）給出相應(yīng)的解決方案，易于理解和修改； ? 估算解決方案的開(kāi)銷，以事先判斷其可行性； ? 維護(hù)和演化 問(wèn)題求解 ? 通過(guò) ? 問(wèn)題抽象 ? 數(shù)據(jù)抽象 ? 算法抽象 分析問(wèn)題，應(yīng)用數(shù)據(jù)結(jié)構(gòu)和算法來(lái)設(shè)計(jì)和實(shí)現(xiàn)高效的程序 問(wèn)題求解 ? 例子 ? 從一組人中找出最高、最矮，及身高最適中的人。 數(shù)據(jù)結(jié)構(gòu) ? 數(shù)據(jù)的邏輯結(jié)構(gòu) ? 關(guān)系 S闡明數(shù)據(jù)結(jié)構(gòu)的特性 ? 集合 ? 同屬于一個(gè)集合 ? 線性結(jié)構(gòu)（ linear structure） ? 一個(gè)對(duì)一個(gè) ? 線性關(guān)系；有向的；全序性和單索性 ? 樹(shù)形結(jié)構(gòu)（ tree structure） ? 一個(gè)對(duì)多個(gè) ? 層次關(guān)系；根節(jié)點(diǎn)；子結(jié)點(diǎn)和父結(jié)點(diǎn) ? 圖狀結(jié)構(gòu)（ graph structure） ? 多個(gè)對(duì)多個(gè) ? 網(wǎng)狀關(guān)系； 數(shù)據(jù)結(jié)構(gòu) ? 數(shù)據(jù)的存儲(chǔ)（物理）結(jié)構(gòu) ? 數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器中的實(shí)現(xiàn)（ 邏輯結(jié)構(gòu)在存儲(chǔ)器中的映象） ? 對(duì)于數(shù)據(jù)邏輯結(jié)構(gòu)（ D , S ） ? “數(shù)據(jù)元素”的映象 ? 對(duì)它的結(jié)點(diǎn)集合 D建立一個(gè)從 D到存儲(chǔ)器的單元的映射：對(duì)于每一個(gè)結(jié)點(diǎn) d∈ D都對(duì)應(yīng)一個(gè) 唯一的連續(xù)存儲(chǔ)區(qū)域 。realPart ) 初始條件：復(fù)數(shù)已存在。 } ADT Complex ? 對(duì)特定問(wèn)題求解過(guò)程的描述，是指令的有限序列，也即，為解決某一特定問(wèn)題而采取的有限的操作步驟。運(yùn)行時(shí)間的下界 ? 最壞運(yùn)行時(shí)間 同樣的輸入規(guī)模，不同的數(shù)據(jù)分布情況下，最慢或運(yùn)行步數(shù)最多時(shí)的運(yùn)行時(shí)間。 ? 若 f(n)=Θ(g(n))，則一定有 f(n)=O(g(n))，反之不成立 漸近記號(hào) O The curves for f(n)=O(g(n)) 漸近記號(hào) O 例子： an3+bn2++d= O(n3), a0 例子： an2+bn+c= O(n3), a0 例子： nlgn＝ O(n2), 但是 nlgn≠Θ(n2) 漸近記號(hào) Ω Ω notation: 定義 ：給定一個(gè)函數(shù) g(n)， Ω (g(n))表示一個(gè)函數(shù)集合 Ω (g(n))＝｛ f(n)|存在正常數(shù) C和 n0使得當(dāng) n≥ n0，均有 0≤Cg(n)≤f(n)成立 ｝ 。 g(n)= (3) f(n)=nlogn+n。 g(n)=3n n附加：常見(jiàn)函數(shù) 簡(jiǎn)單函數(shù) ① na n的多項(xiàng)式函數(shù)
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1