71304數(shù)據(jù)結(jié)構(gòu)-資料下載頁
2024-09-30 09:39本頁面
【導(dǎo)讀】授課學(xué)時(shí)：32學(xué)時(shí)。答疑地點(diǎn)：計(jì)算機(jī)樓532，每周1次。期末筆試80%+平時(shí)成績20%. 期末考試實(shí)行開卷方式。從布置作業(yè)起，到下一次課前兩天。電子版，提交到教務(wù)處網(wǎng)站上的課程中心。文件命名，文件格式，大小≤500K. 殷人昆,《數(shù)據(jù)結(jié)構(gòu)——用面向?qū)ο蠓椒ㄅc。金遠(yuǎn)平，《數(shù)據(jù)結(jié)構(gòu)C++描述》，清華大學(xué)出版社?？佳小⒄夜ぷ黜殢?fù)習(xí)的一門課。算法性能分析與度量。信息的載體（殷人昆）。描述事物的符號(hào)記錄（維基）。在計(jì)算機(jī)科學(xué)中，數(shù)據(jù)指能輸入到計(jì)算機(jī)中并被計(jì)。算機(jī)程序識(shí)別和處理的符號(hào)的集合。數(shù)據(jù)的基本單位。進(jìn)行考慮和處理。如學(xué)生組成班級(jí)，學(xué)生是數(shù)據(jù)元素，班級(jí)是學(xué)生集。數(shù)據(jù)元素及其之間的抽象關(guān)系。數(shù)據(jù)及其邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示，實(shí)質(zhì)上。由其他數(shù)據(jù)類型組成，并包括一組相關(guān)操作。抽象數(shù)據(jù)類型三大特征。減少接口復(fù)雜性，從而減少出錯(cuò)機(jī)會(huì)。改局部化，提高系統(tǒng)靈活性?！鞍馘X買百雞”問題：公雞每只5錢，母雞每只3. 令公雞母雞小雞分別為x,y,z只
【正文】 表示法：若存在兩個(gè)正的常數(shù) c和 n0，對(duì)于任意 n≥n0，都有 T(n) ≤ c f(n)，則稱 T(n)=O(f(n)) ? 例 2： T(n) = 10n2+4n+2 ? 當(dāng) n≥2時(shí)， 10n2+4n+2 ≤ 10n2+5n ? 又有當(dāng) n≥5時(shí)， 10n2+5n ≤ 10n2+n2 = 11n2 ? 因此 T(n)=O(n2) 33 算法性能分析與度量 ? 算法的時(shí)間復(fù)雜度 ? 大 O表示法：若存在兩個(gè)正的常數(shù) c和 n0，對(duì)于任意 n≥n0，都有 T(n) ≤ c f(n)，則稱 T(n)=O(f(n)) ? 作業(yè)：求解 T(n) = amnm+am1nm1+ ??? a2n2+a1n+a0，并給出證明過程 34 算法性能分析與度量 ? 算法的時(shí)間復(fù)雜度 ? T(n)=O(f(n)) ? 若存在兩個(gè)正的常數(shù) c和 n0，對(duì)于任意 n≥n0，都有T(n) ≤ c f(n)，則稱 T(n)=O(f(n)) ? 給出算法復(fù)雜度的上界，不可能比 c*f(n)更大 ? 例： T(n) = 6*2n+n2 ? 當(dāng) n≥4時(shí)， 6*2n+n2 ≤ 6*2n+2n = 7*2n ? 因此 T(n)=O(2n) 35 算法性能分析與度量 ? 算法的時(shí)間復(fù)雜度 ? T(n)=Ω(f(n)) ? 若存在 c 0，和正整數(shù) n0≥1，使得當(dāng) n≥n0時(shí)， 有T(n)≥c*f(n)成立。 ? 給出算法復(fù)雜度的下界，不可能比 c*f(n)更小 ? 例： T(n)=3n3+2n2，取 c=3， n0=1， f(n)=n3，則當(dāng) n≥n0(=1)時(shí)，有 3n3+2n2≥3n3， ∴ T(n)=Ω(n3) 36 算法性能分析與度量 ? 算法的時(shí)間復(fù)雜度 ? T(n)=?(f(n)) ? 若存在 c1,c20，和正整數(shù) n0≥1，使得當(dāng) n≥n0時(shí)，總有 T(n)≤c1*f(n)且 T(n)≥c2*f(n)成立，即 T(n)=O(f(n))與T(n)=Ω(f(n))都成立。 ? 給出了算法時(shí)間復(fù)雜度的上界 和 下界 ? (n)= 3n3+2n2， c1=5，取 c2=3， n0=1， f(n)=n3，則當(dāng) n≥n0(=1)時(shí)，有 3n3+2n2≤5n3及 3n3+2n2≥3n3（無窮多個(gè)）， ∴ T(n)= ? (n3) 37 算法性能分析與度量 ? 算法的時(shí)間復(fù)雜度 ? 常見的時(shí)間復(fù)雜度 ? Ο(1)≤Ο(log2n) ≤Ο(n) ≤Ο(nlog2n) ≤Ο(n2) ≤Ο(n3) ≤… ≤Ο(2n) ≤Ο(n!) 38 T(n) n 0 2n n3 n n2 logn 算法性能分析與度量 ? 算法的空間復(fù)雜度 ? 指算法在執(zhí)行過程中所需最大存儲(chǔ)空間 ? 空間復(fù)雜性的漸進(jìn)分析 39 S(n)=O(f(n)) O(log2n) ?= O(log3n) O(2n) ?= O(3n)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1