算法設(shè)計(jì)技巧與分析第1章算法基本概念之計(jì)算法(參考版)
2025-01-09 18:36本頁面
【正文】 ——高斯 算法 輸入 輸出 時(shí)間復(fù)雜度 FIRST n、 A[1 ??nj i1Analysis ? 數(shù)論：是研究數(shù)的性質(zhì)的一門學(xué)科。 輸出 : ??nj jA1 ][ sum ← 0 for j ← 1 to n sum ← sum + A [ j ] end for return sum sum ← 0 for j ← 1 to n sum ← sum + j end for return sum 輸入 : 正整數(shù) n 。 ? 輸入的大小作為一個(gè)數(shù)量，不是輸入的精確測(cè)度，它解釋為從屬于已設(shè)計(jì)或?qū)⒁O(shè)計(jì)的算法的問題。i]中的概率是 1/i ，則 將 A[i]插入到 A[1 ? 則 ： 要將元素 A[i]插入 A[1 ? 假定 2： 數(shù)字 1， 2， 3， ? 假定 1： A[ , [ ]y A y A j??? 則 ： 為找到 x 位置，執(zhí)行的比較次數(shù)的平均值是 : 這表明在平均情況下，為找到 x 位置，算法要執(zhí)行（ n+1)/2 次元素比較，因此算法LINEARSEARCH的時(shí)間復(fù)雜性在平均情況下是 的。]包含 1到 n，這意味著所有 A中的元素都是不同的。 Example ? 考察對(duì)象 ： 算法 LINEARSEARCH的平均情況。 ? 需要預(yù)先知道輸入的分布，即所有輸入出現(xiàn)的概率。 ? 注意 ： ? 對(duì)于 n的無限多個(gè)值運(yùn)行時(shí)間是 Ω(n)的，并不意味著在最壞情況下運(yùn)行時(shí)間是 Ω(n)的。 考慮：最壞情況下 ， 算法 LINEARSEARCH的運(yùn)行時(shí)間是不是 Ω(n) 的？ Analysis ? 證明 ： 不存在一個(gè)閾值 ,使對(duì)所有的 ，都存在某一大小為 n的輸入，使算法對(duì)于某一常數(shù) c至少用 的時(shí)間。 注意：并不是所有的算法在最壞情況下的上下界總會(huì)重合！ Example ? 輸入 ：一個(gè)元素 x和一個(gè)有 n個(gè)元素的排序數(shù)組 A。 ? 考慮 ： ? a: 數(shù)組 A中的元素已按降序排列； ? b: 數(shù)組 A中的元素為隨機(jī)順序； ? c: 數(shù)組 A中的元素已按升序排列； Figure 輸入大小 運(yùn)行時(shí)間 最好情況 平均情況 最壞情況 n2/2 n2/4 n Worst ? 在最壞情況假設(shè)下，許多算法的上下界合一。 ? 平均情況分析 ： ? 考慮所有大小為 n的輸入的平均時(shí)間。注意，在這個(gè) 例子中，能夠通過對(duì)循環(huán)次數(shù)計(jì)數(shù)來獲得運(yùn)行時(shí) 間的精確測(cè)度，這是因?yàn)樵诿恳粋€(gè)循環(huán)中算法用 的時(shí)間量不變，循環(huán)的總數(shù)是 k+(nk)=n。 1. prod ← 1 。 Meta Operation Count 二分搜索 選擇排序 插入排序 合并排序 Example 已知 ： 有一個(gè) n 個(gè)整數(shù)的數(shù)組 A[1函數(shù) ADD (n) 、 SUB (n) 、MUL (n) 、 DIV (n)分別表示程序 P中，所使用的加、減、乘、除運(yùn)算的次數(shù)。 令 n代表程序的實(shí)例特征，那
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號(hào)-1