算法與算法分析ppt課件(已修改)
2025-05-11 03:58 本頁面
【正文】 1 ? 第一章 緒論 引言 算法 及算法分析（算法評價） 2 什么是算法？ ? 算法是對 解決問題 的 方法 的一種 精確描述 。 ? 并非所有問題都有算法，有些問題經(jīng)研究可行，則可能有相應(yīng)算法；而有些問題經(jīng)研究不可行，則沒有相應(yīng)算法。 ? 因此，算法研究在某種意義上就是可行性研究。 3 算法的性質(zhì) ? 算法可以理解為動作序列的有限集合 ? 僅有一個初始動作 ? 每個動作的后繼動作是確定的 ? 算法的終止表示問題得到解答或問題沒有解答 5 1． 有窮性 對于任意一組合法輸入值，在執(zhí)行 有窮步驟 之后一定能結(jié)束，即： 算法中的每個步驟都能在 有限時間 內(nèi)完成。 2． 確定性 對于 每種情況 下所應(yīng)執(zhí)行的操作，在算法中都有 確切 的規(guī)定，使算法的執(zhí)行者或閱讀者都能明確其含義及如何執(zhí)行。 并且 在任何條件下，算法都只有一條執(zhí)行路徑。 6 3． 可行性 算法中的所有操作都必須 足夠基本 ，都可以通過已經(jīng)實現(xiàn)的基本操作運算有限次實現(xiàn)之。 4． 有輸入 作為算法加工對象的量值，通常體現(xiàn)為算法中的一組變量。有些輸入量需要在算法執(zhí)行過程中輸入，而有的算法表面上可以沒有輸入，實際上已被嵌入算法之中。 7 5． 有輸出 它是一組與 “ 輸入 ” 有確 定關(guān)系的量值，是算法進(jìn)行信息加工后得到的結(jié)果，這種確定關(guān)系即為算法的功能。 8 算法設(shè)計的原則 設(shè)計算法時，通常應(yīng)考慮達(dá)到以下目標(biāo)： 1． 正確性 2. 可讀性 3． 健壯性 4． 高效率與低存儲量需求 9 1． 正確性 首先， 算法應(yīng)當(dāng) 滿足 以特定的 “ 規(guī)格說明 ” 方式給出的 需求 。 其次， 對算法是否 “ 正確 ” 的 理解可以有以下 四個層次 ： a． 程序中不含語法錯誤； b． 程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果； 10 c． 程序?qū)τ诰倪x擇的、典型、苛刻且?guī)в械箅y性的幾組輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果； 通常以 第 c 層 意義的正確性作為衡量一個算法是否合格的標(biāo)準(zhǔn)。 d． 程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能得出滿足要求的結(jié)果； 11 2. 可讀性 算法主要是為了人的 閱讀與交流 ， 其次才是為計算機(jī)執(zhí)行，因此算法應(yīng)該 易于 人的 理解 ；另一方面，晦澀難讀的程序易于隱藏較多錯誤而難以調(diào)試。 12 3． 健壯性 當(dāng) 輸入的數(shù)據(jù) 非法 時，算法應(yīng)當(dāng)恰當(dāng)?shù)刈鞒龇从郴?進(jìn)行相應(yīng)處理 ，而不是產(chǎn)生莫名奇妙的輸出結(jié)果。并且， 處理出錯的方法 不應(yīng)是中斷程序的執(zhí)行，而應(yīng)是 返回 一個 表示錯誤或錯誤性質(zhì)的值 ，以便在更高的抽象層次上進(jìn)行處理。 13 4． 高效率與低存儲量需求 通常，效率指的是 算法執(zhí)行時間 ； 存儲量指的是算法執(zhí)行過程中 所需的 最大存儲空間 ，兩者都與問題的規(guī)模 有關(guān)。 14 ? 第一章 緒論 引言 算法及 算法分析 （算法評價） 15 算法分析與算法復(fù)雜度 ? 算法分析的任務(wù)是對設(shè)計出的每一個具體的算法，利用數(shù)學(xué)工具，討論其復(fù)雜度，探討具體算法對問題的適應(yīng)性 ? 算法的復(fù)雜度分時間復(fù)雜度和空間復(fù)雜度。 ? 計算機(jī)理論科學(xué)中，按照計算復(fù)雜性研究問題求解的難易性，可把問題分為 P類、 NP類 和 NP完全類。 16 算法的效率 對于一個問題通常有多種解法（算法），應(yīng)該選擇哪一種呢？ 計算機(jī)程序設(shè)計的核心有兩個目標(biāo)（有時它們互相沖突） 1. 設(shè)計一種容易理解、編碼和調(diào)試的算法 2. 設(shè)計一種能有效利用計算機(jī)資源的算法 17 算法的效率 (cont) 目標(biāo) 1涉
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1