算法引論ppt課件-閱讀頁(yè)
2025-05-14 03:59本頁(yè)面
【正文】 是 Θ以盡可能簡(jiǎn)單的形式進(jìn)行表示。退而求其次，可以使用 O或是 Ω。 ? 使用 Ω時(shí)，希望估計(jì)的下界的階越大越好。因此計(jì)算程序的迭代次數(shù)就可以作為算法運(yùn)行時(shí)間的指示器。 南京理工大學(xué) 計(jì)算迭代次數(shù) 輸入： n (n = 2k ， k 為某一正整數(shù) ) 輸出： count 1. count ← 0 2. while n ≥ 1 3. for j ← 1 to n 4. count ← count+1 //執(zhí)行一次耗費(fèi)時(shí)間設(shè)為 a 5. end for 6. n ← n/2 //執(zhí)行一次耗費(fèi)時(shí)間設(shè)為 d 7. end while 8. return count 分析： while 迭代的次數(shù)是 k +1次 (因?yàn)?n≥1 可以寫成 n≥20, 運(yùn)行過(guò)程n=2k→2 0)， k = log n 。 南京理工大學(xué) 例： 輸入：正整數(shù) n 輸出： step 5 的執(zhí)行次數(shù) 1. count ← 0 2. for i ← 1 to n 3. m← ?n/i? 4. for j ← 1 to m 5. count ← count+1 6. end for 7. end for 8. return count 分析： Step5 的執(zhí)行次數(shù)依次為： n, ?n/2?, ?n/3?, …, ?n/n? 1() ninTni???? ?????1 1 1( 1 )n n ni i in n ni i i? ? ???? ? ?????? ? ?因?yàn)? ( ) ( lo g )T n n n??所以 南京理工大學(xué) 2 使用遞歸方程 2l og11()( / 2 ) 1 2( ) ( / 2 ) 1 ( / 2 ) 1 1( / 2 ) l og 1 l og ( l og )nif nTnT n if nT n T n T nT n n n n???????? ?????? ?????? ? ? ? ? ????? ????? ? ? ? ? ?? ? ? ?? ? ? ???輸入： 非降序排列的數(shù)組 A[1…n] 和元素 x 輸出：如果 x=A[j], 1 ?j ?n,則輸出 j,否則輸出 0. 1. low←1。 j←0 2. while(low ?high) and (j=0) 3. mid ← ?( low+high)/2? 4. if x=A[mid] then j ←mid 5. else if xA[mid] then high ←mid 1 6. else low ←mid+1 7. end while 8. return j 南京理工大學(xué) 3 頻度分析 ? 對(duì)于有些算法，要像前面那樣準(zhǔn)確地分析算法的運(yùn)行時(shí)間非常麻煩，有時(shí)甚至是不可能的。 (單源最短路徑、 Prim 算法等等 ) 南京理工大學(xué) 算法復(fù)雜度分析的意義 ? 已知待求解問(wèn)題的多種算法時(shí)，挑選復(fù)雜度盡可能低的算法進(jìn)行應(yīng)用。 ? 設(shè)計(jì)出算法后，不要急于實(shí)現(xiàn)，而是先進(jìn)行復(fù)雜度分析后；若該算法確實(shí)可行，才有實(shí)現(xiàn)的價(jià)值與必要。有的人因此認(rèn)為不必要再去苦苦追求高效率的算法。 ? 造成上述錯(cuò)誤認(rèn)識(shí)的原因是他們沒(méi)看到：隨著經(jīng)濟(jì)的發(fā)展、社會(huì)的進(jìn)步、科學(xué)研究的深入，要求計(jì)算機(jī)解決的問(wèn)題越來(lái)越復(fù)雜、規(guī)模越來(lái)越大，也呈增長(zhǎng)之勢(shì)；而問(wèn)題復(fù)雜程度和規(guī)模的線性增長(zhǎng)導(dǎo)致的時(shí)耗的增長(zhǎng)和空間需求的增長(zhǎng)，對(duì)低效算法來(lái)說(shuō)，都是非線性的，決非計(jì)算機(jī)速度和容量的線性增長(zhǎng)帶來(lái)的時(shí)耗減少和存儲(chǔ)空間的擴(kuò)大所能抵銷。 – 復(fù)雜度分別為 n3與 10n2：當(dāng) n10時(shí)， n310n2。 ? 在問(wèn)題規(guī)模較小時(shí)，我們往往并不一味追求低復(fù)雜度的算法，而是更側(cè)重于算法的簡(jiǎn)單性。 – 例如：復(fù)雜度為 n1ogn/l00 的算法顯然比復(fù)雜度為 l00n1ogn 的算法
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1