算法與算法分析ppt課件(編輯修改稿)
2025-05-26 03:58 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 ) 增長(zhǎng)率的上限用符號(hào) O表示，稱為大 O表示法(bigOh notation). Example: If T(n) = 3n2 then T(n) is in O(n2). 希望最“緊”（即最?。┑纳舷?: 雖然 T(n) = 3n2 可以說(shuō)它在 O(n3)中 , 我們更喜歡用 O(n2). 32 上限的例子 例 1:考慮找出整數(shù)數(shù)組中某個(gè)元素的順序檢索法 (average cost). 如果訪問(wèn)并檢查數(shù)組中的一個(gè)元素需要時(shí)間cs (cs為常數(shù) )， 那么在平均情況下 T(n) = csn/2 。 當(dāng) n 1時(shí)， csn/2 = csn ， 所以根據(jù)定義， T(n)在 O(n)中， n0 =1， c = cs 33 上限的例子 例 2:某一算法平均情況下 T(n) = c1n2 + c2n. c c2為正數(shù)。 當(dāng) n 1， c1n2 + c2n = c1n2 + c2n2 = (c1 + c2)n2. 因此取 c = c1 + c2 and n0 = 1， 有 T(n) = 2. 所以根據(jù)定義 , T(n) 在 is in O(n2) 中 . 例子 3: T(n) = c. 我們說(shuō)它在 O(1)中 . 34 BigOmega 定義 :對(duì)于非負(fù)函數(shù) T(n) ， 若存在兩個(gè)正常數(shù)c和 and n0 ， 使得當(dāng) n n0 時(shí)有 T(n) = cg(n) ， 則稱 T(n) 在集合 ?(g(n))中 意義 : 對(duì)于問(wèn)題的所有 [最佳、平均、最差情況 ]輸入，只要輸入規(guī)模足夠大 (即 nn0),該算法的完成至少需要 cf(n)步 . 下限 . 35 BigOmega Example 例 1：假定 T(n) = c1n2 + c2n. (c1， c20) 則有 c1n2 + c2n = c1n2 for all n 1. 因此，取 c = c1 ， n0 = 1 ， 有 T(n) = 2. 所以 ,根據(jù)定義 , T(n) 在 ?(n2)中 也可以說(shuō) T(n)在 ?(n)中 我們希望找到一個(gè)最“緊”的可能限制 .（ 最大下限） 36 Theta Notation 上限和下限描述了算法運(yùn)行時(shí)間的范圍 當(dāng)上、下限相等時(shí)，可以用 ?表示法 定義 : 如果非負(fù)函數(shù) T(n)既在 O(h(n))中，又在?(h(n))中，則稱算法 T(n)是 ?(h(n))。 這時(shí)也說(shuō) T(n)與 h(n)同階 37 A Common Misunderstanding “算法最佳情況是輸入規(guī)模為 1時(shí)，因?yàn)檫@時(shí)運(yùn)行最快”。錯(cuò)誤！ 大 O指的是當(dāng) n趨近于 ?時(shí)的增長(zhǎng)率 最佳情況指的是在規(guī)模為 n的所有輸入中 哪個(gè)輸入運(yùn)行最快。 38 A Common Misunderstanding 混淆了最差情況和上限 上限指的是增長(zhǎng)率 最差情況指的是給定規(guī)模的所有可能輸入中最差的輸入，消耗（運(yùn)行）的時(shí)間最大 39 Simplifying Rules 1. If f(n) is in O(g(n)) and g(n) is in O(h(n)), then f(n) is in O(h(n)). 2. If f(n) is in O(kg(n)) for any constant k 0, then f(n) is in O(g(n)). 3. If f1(n) is in O(g1(n)) and f2(n) is in O(g2(n)), then (f1 + f2)(n) is in O(max(g1(n), g2(n))). 4. If f1(n) is in O(g1(n)) and f2(n) is in O(g2(n)) then f1(n)f2(n) is in O(g1(n)g2(n)). 40 程序運(yùn)行時(shí)間的計(jì)算 (1) Example 1: a = b。 This assignment takes constant time, so it is ?(1). Example 2: sum =
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1