算法與算法分析ppt課件(存儲(chǔ)版)
【正文】 時(shí)間復(fù)雜性（續(xù)） 更快的計(jì)算機(jī)，還是更快的算法 ? 27 時(shí)間復(fù)雜度對(duì)解題速度的影響 O(n) 解 題 速 度 n = 10 n = 30 n = 60 n ms ms ms n2 ms ms ms n5 s s min 2n ms min 世紀(jì) 3n s 年 1013 世紀(jì) 28 ? 阿達(dá)爾定律 設(shè) f 為求解某個(gè)問(wèn)題的計(jì)算存在的必須串行執(zhí)行的操作占整個(gè)計(jì)算的百分比， p 處理機(jī)的數(shù)目， Sp 為并行計(jì)算機(jī)系統(tǒng)最大的加速能力（單位：倍），則 設(shè) f =1%， p ? ?， 則 Sp =100。 This assignment takes constant time, so it is ?(1). Example 2: sum = 0。 j=i。 i++) for (j=1。 j++) sum2++。 for (k=1。 i++) // Initialize count count[i] = 0。 d = a + e。 for(i=0。j++) A[i] = Random(n)。j++) sum3++。 時(shí)間代價(jià)為 ?(n) 55 課堂練習(xí) 1. The primary purpose of most puter programs is a) to perform a mathematical calculation. b) to store and retrieve information. c) to sort a collection of records. d) all of the above. e) none of the above. 2. An algorithm must be or do all of the following EXCEPT: a) correct b) posed of concrete steps c) ambiguous d) posed of a finite number of steps e) terminate 56 3. Asymptotic analysis refers to: a) The cost of an algorithm in its best, worst, or average case. b) The growth in cost of an algorithm as the input size grows towards infinity. c) The size of a data structure. d) The cost of an algorithm for small input sizes 4. Pick the growth rate that corresponds to the most efficient algorithm as n gets large: a) 5n b) 20 log n c) 2n^2 d) 2^n 。i++) for(j=0。i++){ for(j=0。j++) sum++。 請(qǐng)郵件告訴我（ ） 52 習(xí)題講解 寫(xiě)出下列程序段平均情況下時(shí)間代價(jià)的 ?表示式。又內(nèi)層循環(huán)執(zhí)行次數(shù)恒為 n， 所以第一段程序的總時(shí)間代價(jià)可表示為 n(1+logn), 即Θ(nlogn) 外層 for循環(huán)當(dāng) i=1, 2, 22, …, 2k=n時(shí)執(zhí)行 , 而內(nèi)層循環(huán)執(zhí)行 k次，所以第二段程序的總時(shí)間代價(jià)可表示為1+2+22+ …+ 2k= , 由公式 ，其和為2k+11, 因?yàn)?k=logn, 所以總時(shí)間代價(jià)為 2n1, 即 Θ(n) 44 其他控制語(yǔ)句 ? while循環(huán)、 dowhile循環(huán) – 分析方法與 for循環(huán)類似 ? if語(yǔ)句 – 最差情況時(shí)間代價(jià)是 then和 else部分中時(shí)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1