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