jnqaaaalgorithm-chapter-(編輯修改稿)
2025-08-20 13:01 本頁面
【文章內容簡介】 ∈ O(max{(g1(n), g2(n)}) ?對于符號 Ω和 Θ，該定理也成立。 ?該定理表明： 當算法由兩個連續(xù)執(zhí)行部分組成時，該算法的整體效率由具有較大增長次數的那部分所決定。 Analysis and Design of Computer Algorithms Yunnan University School of Information Science amp。 Engineering 13 利用極限比較增長次數 前兩種情況意味著 t(n) ∈ O(g(n)) 后兩種情況意味著 t(n) ∈ Ω(g(n)) 第二種情況意味著 t(n) ∈ Θ(g(n)) Analysis and Design of Computer Algorithms Yunnan University School of Information Science amp。 Engineering 14 基本的效率類型 常量 (1)、對數 (logn)、線性(n)、 nlogn、平方 (n2)、立方 (n3)、指數 (2n)、階乘 (n!) Analysis and Design of Computer Algorithms Yunnan University School of Information Science amp。 Engineering 15 非遞歸算法的數學分析 ?Example 1：討論下面這個算法（從 n個元素中查找最大元素問題）的效率。 算法 MaxElement(A[0..n1] //求給定數組中的最大元素 //輸入：實數數組 A[0..n1] //輸出： A中的最大元素 maxval ?A[0] for i ? 1 to n1 do if A[i] maxval maxval ? A[i] return maxval 考慮： 1. 循環(huán)中的操作有 比較 和 賦值 ，取哪一個作為基本操作？ 2. 輸入規(guī)模是多少？ 基本操作為：比較運算 輸入規(guī)模就是數組長度 n 算法的效率為： Analysis and Design of Computer Algorithms Yunnan University School of Information Science amp。 Engineering 16 分析非遞歸算法效率的通用方案 1. 決定用那些參數作為輸入規(guī)模的度量。 2. 找出算法的基本操作。 3. 檢查基本操作的執(zhí)行次數是否只依賴輸入規(guī)模。 4. 建立一個算法基本操作執(zhí)行次數的求和表達式。 5. 利用求和運算的標準公式和法則來建立一個操作次數的閉合公式，或者至少確定它的增長次數。 Analysis and Design of Computer Algorithms Yunnan University School of Information Science amp。 Engineering 17 Example 考慮下面算法的效率 ?Example 2 元素唯一性問題 算法 UniqueElements(A[0..n1]) //驗證給定數組的元素是否全部唯一 //輸
環(huán)評公示相關推薦
鄂ICP備17016276號-1