算法設(shè)計(jì)技巧與分析第1章算法基本概念之計(jì)算法-文庫(kù)吧資料
2025-01-12 18:36本頁(yè)面
【正文】 么 TP的計(jì)算公式為： TP（ n） = c1ADD(n) + c2SUB(n) + c3MUL(n) + c4DIV(n)+ ? 方法：用執(zhí)行這些運(yùn)算的總次數(shù)的函數(shù)來(lái)表示運(yùn)行時(shí)間。 )( 2nOSpecial Instance ? 在有些算法里，所有的元運(yùn)算都不是基本運(yùn)算。 ( log )nn?Why？ )( 2nO? 注意 ：當(dāng)兩個(gè)算法的輸入相同的時(shí)候，算法 MODINSETIONSORT和算法 INSETIONSORT的元素賦值次數(shù)完全一樣，這已被證明是 。 輸出 : 按非降序排列的數(shù)組 A [ 1 ? i– 1 ] 。由此可知，算法的運(yùn)行時(shí)間是 Θ (n log n) 。 ? 舉例 ： ? 算術(shù)運(yùn)算 ? 比較和邏輯運(yùn)算 ? 賦值運(yùn)算 Basic Operation ? 定義 如果算法中的一個(gè)元運(yùn)算具有最高頻度，所有其他元運(yùn)算頻度均在它的頻度的常數(shù)倍內(nèi)，則稱這個(gè)元運(yùn)算為 基本運(yùn)算 。 2k??ji i1 for j ← 1 to k sum [ j ] ← 0 for i ← 1 to j2 end for sum [ j ] ← sum [ j ] + i end for return sum [1 ? k ] k ← nAnalysis ? 考察對(duì)象 1：算法的運(yùn)行時(shí)間； ? 結(jié)論 ：算法的運(yùn)行時(shí)間是 。 ? 結(jié)論 ： 第 6步執(zhí)行次數(shù)為 ( l og l og 1 ) ( l og l og )n n n n? ? ?輸入 : n = , k 為某個(gè)整數(shù)。 k22 count ← 0 for i ← 1 to n j ← 2 while j ≤ n j ← 2j count ← count + 1 end while end for return count Analysis ? 包含 ： 兩個(gè)嵌套循環(huán)和一個(gè)變量 count； ? 輸入 ： n 具有 形式， k 為正整數(shù)。 ( log )nn?? 第 5步的執(zhí)行次數(shù)是： ?? ??????ni in1輸入 : n = , k 為正整數(shù)。 輸出 : 第 5步的執(zhí)行次數(shù) count 。 ， 1 次。 輸出 : 第 4步的執(zhí)行次數(shù) count 。 ? 計(jì)算迭代次數(shù)將很好的表明算法的運(yùn)行時(shí)間，適用于搜索、排序、矩陣乘法等算法。算法設(shè)計(jì)技巧與分析 Algorithms Design Techniques and Analysis 南方醫(yī)科大學(xué)醫(yī)工學(xué)院 信息技術(shù)系 第 1章 算法分析基本概念 Content ? 算法與程序 ? 簡(jiǎn)單的算法實(shí)例 ? 計(jì)算復(fù)雜性 ? 時(shí)間復(fù)雜性 ? 空間復(fù)雜性 ? 分析計(jì)算方法 Methods ? 估算算法運(yùn)行時(shí)間的方法 ： 1）迭代計(jì)數(shù)
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號(hào)-1