算法與算法分析ppt課件-在線瀏覽
2025-06-16 03:58本頁(yè)面
【正文】 算法應(yīng)當(dāng) 滿足 以特定的 “ 規(guī)格說明 ” 方式給出的 需求 。有些輸入量需要在算法執(zhí)行過程中輸入，而有的算法表面上可以沒有輸入，實(shí)際上已被嵌入算法之中。 6 3． 可行性 算法中的所有操作都必須 足夠基本 ，都可以通過已經(jīng)實(shí)現(xiàn)的基本操作運(yùn)算有限次實(shí)現(xiàn)之。 2． 確定性 對(duì)于 每種情況 下所應(yīng)執(zhí)行的操作，在算法中都有 確切 的規(guī)定，使算法的執(zhí)行者或閱讀者都能明確其含義及如何執(zhí)行。 ? 因此，算法研究在某種意義上就是可行性研究。1 ? 第一章 緒論 引言 算法 及算法分析（算法評(píng)價(jià)） 2 什么是算法？ ? 算法是對(duì) 解決問題 的 方法 的一種 精確描述 。 ? 并非所有問題都有算法，有些問題經(jīng)研究可行，則可能有相應(yīng)算法；而有些問題經(jīng)研究不可行，則沒有相應(yīng)算法。 3 算法的性質(zhì) ? 算法可以理解為動(dòng)作序列的有限集合 ? 僅有一個(gè)初始動(dòng)作 ? 每個(gè)動(dòng)作的后繼動(dòng)作是確定的 ? 算法的終止表示問題得到解答或問題沒有解答 5 1． 有窮性 對(duì)于任意一組合法輸入值，在執(zhí)行 有窮步驟 之后一定能結(jié)束，即： 算法中的每個(gè)步驟都能在 有限時(shí)間 內(nèi)完成。 并且 在任何條件下，算法都只有一條執(zhí)行路徑。 4． 有輸入 作為算法加工對(duì)象的量值，通常體現(xiàn)為算法中的一組變量。 7 5． 有輸出 它是一組與 “ 輸入 ” 有確 定關(guān)系的量值，是算法進(jìn)行信息加工后得到的結(jié)果，這種確定關(guān)系即為算法的功能。 其次， 對(duì)算法是否 “ 正確 ” 的 理解可以有以下 四個(gè)層次 ： a． 程序中不含語(yǔ)法錯(cuò)誤； b． 程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果； 10 c． 程序?qū)τ诰倪x擇的、典型、苛刻且?guī)в械箅y性的幾組輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果； 通常以 第 c 層 意義的正確性作為衡量一個(gè)算法是否合格的標(biāo)準(zhǔn)。 12 3． 健壯性 當(dāng) 輸入的數(shù)據(jù) 非法 時(shí)，算法應(yīng)當(dāng)恰當(dāng)?shù)刈鞒龇从郴?進(jìn)行相應(yīng)處理 ，而不是產(chǎn)生莫名奇妙的輸出結(jié)果。 13 4． 高效率與低存儲(chǔ)量需求 通常，效率指的是 算法執(zhí)行時(shí)間 ； 存儲(chǔ)量指的是算法執(zhí)行過程中 所需的 最大存儲(chǔ)空間 ，兩者都與問題的規(guī)模 有關(guān)。 ? 計(jì)算機(jī)理論科學(xué)中，按照計(jì)算復(fù)雜性研究問題求解的難易性，可把問題分為 P類、 NP類 和 NP完全類。 串行計(jì)算與并行計(jì)算 pffS p???1129 算法分析的任務(wù)是對(duì)設(shè)計(jì)出的每一個(gè)具體的算法，利用數(shù)學(xué)工具，討論其復(fù)雜度，探討具體算法對(duì)問題的適應(yīng)性 ? 算法的時(shí)間復(fù)雜度 ? 規(guī)模 ? 基本操作 ? 增長(zhǎng)率 ? 平均情況 ? 效率 請(qǐng)把下列的術(shù)語(yǔ)融入到上句中， 對(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))中。 當(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ù)。 這時(shí)也說 T(n)與 h(n)同階 37 A Common Misunderstanding “算法最佳情況是輸入規(guī)模為 1時(shí)，因?yàn)檫@時(shí)運(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
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1