算法與算法分析ppt課件-wenkub
2023-05-14 03:58:15 本頁面
【正文】 作為算法加工對象的量值，通常體現(xiàn)為算法中的一組變量。 3 算法的性質(zhì) ? 算法可以理解為動作序列的有限集合 ? 僅有一個(gè)初始動作 ? 每個(gè)動作的后繼動作是確定的 ? 算法的終止表示問題得到解答或問題沒有解答 5 1． 有窮性 對于任意一組合法輸入值，在執(zhí)行 有窮步驟 之后一定能結(jié)束，即： 算法中的每個(gè)步驟都能在 有限時(shí)間 內(nèi)完成。1 ? 第一章 緒論 引言 算法 及算法分析（算法評價(jià)） 2 什么是算法？ ? 算法是對 解決問題 的 方法 的一種 精確描述 。 2． 確定性 對于 每種情況 下所應(yīng)執(zhí)行的操作，在算法中都有 確切 的規(guī)定，使算法的執(zhí)行者或閱讀者都能明確其含義及如何執(zhí)行。有些輸入量需要在算法執(zhí)行過程中輸入，而有的算法表面上可以沒有輸入，實(shí)際上已被嵌入算法之中。 d． 程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能得出滿足要求的結(jié)果； 11 2. 可讀性 算法主要是為了人的 閱讀與交流 ， 其次才是為計(jì)算機(jī)執(zhí)行，因此算法應(yīng)該 易于 人的 理解 ；另一方面，晦澀難讀的程序易于隱藏較多錯(cuò)誤而難以調(diào)試。 14 ? 第一章 緒論 引言 算法及 算法分析 （算法評價(jià)） 15 算法分析與算法復(fù)雜度 ? 算法分析的任務(wù)是對設(shè)計(jì)出的每一個(gè)具體的算法，利用數(shù)學(xué)工具，討論其復(fù)雜度，探討具體算法對問題的適應(yīng)性 ? 算法的復(fù)雜度分時(shí)間復(fù)雜度和空間復(fù)雜度。 用法 : 這個(gè)算法 [最佳、平均、最差 ]情況（下的增長率的上限）在 O(n2)中 . 含意 : 對于問題的所有 [最佳、平均、最差情況 ]輸入，只要輸入規(guī)模足夠大 (即 nn0), 該算法總能在 cf(n) 步以內(nèi)完成 . 31 上限 :大 O (cont) 增長率的上限用符號 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 。錯(cuò)誤！ 大 O指的是當(dāng) n趨近于 ?時(shí)的增長率 最佳情況指的是在規(guī)模為 n的所有輸入中 哪個(gè)輸入運(yùn)行最快。 i=n。 i=n。 for (k=0。 for (i=1。 j++) sum1++。 i++) for (j=1。 for (k=1。 j++) sum1++。 k*=2) for (j=1。又內(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 其他控制語句 ? while循環(huán)、 dowhile循環(huán) – 分析方法與 for循環(huán)類似 ? if語句 – 最差情況時(shí)間代價(jià)是 then和 else部分中時(shí)間代價(jià)較大的那一個(gè) – 對于平均情況代價(jià)也是如此 – 假設(shè) n的取值與執(zhí)行哪一條指令的概率無關(guān) ? switch語句 – 最差情況時(shí)間代價(jià)是所有分支中開銷最大的一個(gè) ? 子程序調(diào)用 – 加上執(zhí)行子程序
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1