《算法與算法分析》ppt課件-全文預(yù)覽
【正文】 在 is in O(n2) 中 . 例子 3: T(n) = c. 我們說它在 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ì)于問題的所有 [最佳、平均、最差情況 ]輸入，只要輸入規(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)中 也可以說 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))。 16 算法的效率 對(duì)于一個(gè)問題通常有多種解法（算法），應(yīng)該選擇哪一種呢？ 計(jì)算機(jī)程序設(shè)計(jì)的核心有兩個(gè)目標(biāo)（有時(shí)它們互相沖突） 1. 設(shè)計(jì)一種容易理解、編碼和調(diào)試的算法 2. 設(shè)計(jì)一種能有效利用計(jì)算機(jī)資源的算法 17 算法的效率 (cont) 目標(biāo) 1涉及到軟件工程原理 目標(biāo) 2涉及到數(shù)據(jù)結(jié)構(gòu)與算法分析 本課程主要講的是與目標(biāo) 2有關(guān)的問題 怎樣度量算法的代價(jià)、效率呢？ 19 怎樣比較兩種算法解決問題的效率呢？ ? 實(shí)驗(yàn)比較 – 用源程序分別實(shí)現(xiàn)這兩種算法，然后輸入適當(dāng)?shù)臄?shù)據(jù)運(yùn)行，測(cè)算兩個(gè)程序各自的開銷 – 這是一種事后統(tǒng)計(jì)的方法 ? 漸近算法分析 (asymptotic algorithm analysis)， 簡(jiǎn)稱 算法分析 (algorithm analysis) – 可以估算出當(dāng)問題規(guī)模變大時(shí)，一種算法及實(shí)現(xiàn)它的程序的效率和開銷 – 這是一種事前分析估算的方法 20 “ 規(guī)模 ” 與 “ 基本操作 ” ? 判斷算法性能的一個(gè)基本考慮是處理一定 “ 規(guī)模 ” (size)的輸入時(shí)該算法所需執(zhí)行的 “ 基本操作 ” (basic operation)數(shù) ? “ 規(guī)模 ” 一般是指輸入量的數(shù)目 – 比如，在排序問題中，問題的規(guī)?？梢杂帽慌判蛟氐膫€(gè)數(shù)來衡量 21 “ 規(guī)模 ” 與 “ 基本操作 ” （續(xù)） ? 一個(gè) “ 基本操作 ” 必須具有這樣的性質(zhì)：完成該操作所需時(shí)間與操作數(shù)的具體取值無關(guān) – 在大多數(shù)高級(jí)語(yǔ)言中，下列操作是基本操作： ? 賦值運(yùn)算 ? 簡(jiǎn)單算術(shù)運(yùn)算 ? 簡(jiǎn)單布爾運(yùn)算 ? 簡(jiǎn)單 I／ O操作 ? 函數(shù)返回 – n個(gè)整數(shù)累加不是基本操作 ? 因?yàn)槠浯鷥r(jià)依賴于 n的值 (即大小 ) 22 運(yùn)行時(shí)間和增長(zhǎng)率 ? 由于影響運(yùn)行時(shí)間的最主要因素一般是輸入的規(guī)模，所以經(jīng)常把執(zhí)行算法所需要的時(shí)間 T寫成輸入規(guī)模 n的函數(shù)，記為 T(n) – 我們總是假設(shè) T(n)為非負(fù)值 ? 算法的 增長(zhǎng)率 (growth rate)是指當(dāng)輸入規(guī)模增長(zhǎng)時(shí)，算法代價(jià)的增長(zhǎng)速率 23 最佳、最差和平均情況 不是相同規(guī)模的所有輸入的運(yùn)行時(shí)間都相同 順序搜索法（ Sequential search） 從一個(gè) n元一維數(shù)組中找出一個(gè)給定的值 K : ? 從第一個(gè)元素開始，依次檢索每一個(gè)元素，直到找到 K為止 最佳情況 : 最差情況 : 平均情況 : 24 請(qǐng)用 通俗的例子 談?wù)? 對(duì) 增長(zhǎng)率 和 平均情況 兩個(gè)概念的理解 請(qǐng)郵件告訴我（ ） 25 Growth Rate Graph 26 時(shí)間復(fù)雜性（續(xù)） 更快的
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1