算法與算法分析ppt課件(完整版)
【正文】 算法分析 – 動(dòng)機(jī)：增長率 – 基本符號(hào)： O、 ?、 ? 51 什么情況下，可以直接用 ?表示算法的復(fù)雜度？ 即什么情況下 ， 算法的下限和上限相等 。jn。in。in。 else sum = sum + n。 時(shí)間代價(jià)為 ?(n2logn) 時(shí)間代價(jià)為 = ?(n2) ??nii154 (f)sum = 0。 sort(A,n)。in*n。 (b)sum = 0。 for (i=0。 k=n。 時(shí)間代價(jià)為 ?(n2) 時(shí)間代價(jià)為 ?(n2) 43 程序運(yùn)行時(shí)間的計(jì)算 (4) Example 5: sum1 = 0。 j=n。 j++) sum++。 for (i=1。 串行計(jì)算與并行計(jì)算 pffS p???1129 算法分析的任務(wù)是對(duì)設(shè)計(jì)出的每一個(gè)具體的算法，利用數(shù)學(xué)工具，討論其復(fù)雜度，探討具體算法對(duì)問題的適應(yīng)性 ? 算法的時(shí)間復(fù)雜度 ? 規(guī)模 ? 基本操作 ? 增長率 ? 平均情況 ? 效率 請(qǐng)把下列的術(shù)語融入到上句中， 對(duì)算法分析的任務(wù)進(jìn)行更加清晰的說明 30 漸近分析 :大 O 定義 : 對(duì)于非負(fù)函數(shù) T(n)， 若存在兩個(gè)正常數(shù)c和 n0， 使得當(dāng) nn0時(shí)有 T(n)≤cf(n)， 則稱T(n)在集合 O(f(n))中。 其次， 對(duì)算法是否 “ 正確 ” 的 理解可以有以下 四個(gè)層次 ： a． 程序中不含語法錯(cuò)誤； b． 程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果； 10 c． 程序?qū)τ诰倪x擇的、典型、苛刻且?guī)в械箅y性的幾組輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果； 通常以 第 c 層 意義的正確性作為衡量一個(gè)算法是否合格的標(biāo)準(zhǔn)。 3 算法的性質(zhì) ? 算法可以理解為動(dòng)作序列的有限集合 ? 僅有一個(gè)初始動(dòng)作 ? 每個(gè)動(dòng)作的后繼動(dòng)作是確定的 ? 算法的終止表示問題得到解答或問題沒有解答 5 1． 有窮性 對(duì)于任意一組合法輸入值，在執(zhí)行 有窮步驟 之后一定能結(jié)束，即： 算法中的每個(gè)步驟都能在 有限時(shí)間 內(nèi)完成。 2． 確定性 對(duì)于 每種情況 下所應(yīng)執(zhí)行的操作，在算法中都有 確切 的規(guī)定，使算法的執(zhí)行者或閱讀者都能明確其含義及如何執(zhí)行。 d． 程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能得出滿足要求的結(jié)果； 11 2. 可讀性 算法主要是為了人的 閱讀與交流 ， 其次才是為計(jì)算機(jī)執(zhí)行，因此算法應(yīng)該 易于 人的 理解 ；另一方面，晦澀難讀的程序易于隱藏較多錯(cuò)誤而難以調(diào)試。 用法 : 這個(gè)算法 [最佳、平均、最差 ]情況（下的增長率的上限）在 O(n2)中 . 含意 : 對(duì)于問題的所有 [最佳、平均、最差情況 ]輸入，只要輸入規(guī)模足夠大 (即 nn0), 該算法總能在 cf(n) 步以內(nèi)完成 . 31 上限 :大 O (cont) 增長率的上限用符號(hào) O表示，稱為大 O表示法(bigOh notation). Example: If T(n) = 3n2 then T(n) is in O(n2). 希望最“緊”（即最小）的上限 : 雖然 T(n) = 3n2 可以說它在 O(n3)中 , 我們更喜歡用 O(n2). 32 上限的例子 例 1:考慮找出整數(shù)數(shù)組中某個(gè)元素的順序檢索法 (average cost). 如果訪問并檢查數(shù)組中的一個(gè)元素需要時(shí)間cs (cs為常數(shù) )， 那么在平均情況下 T(n) = csn/2 。 i=n。 for (k=0。 j++) sum1++。 for (k=1。 k*=2) for (j=1。 iP。 for(i=0。i++) sum++。 } (e)假設(shè)數(shù)組 A中元素為從 0到 n－ 1的任意一個(gè)排列。 if(EVEN(n)) for(i=0。i++) sum++。 for(i=0。 for(i=0。i++)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1