演算法复杂度分析范例.PPT

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 插入排序演算法(續) * 插入排序演算法(續) 在整個插入排序演算法的執行過程中，8 與 8’的相對位置一直保持不變，因此插入排序演算法也是一個穩定(stable)排序演算法。 除了幾個索引變數與一個陣列數值臨時儲存變數之外，插入排序演算法不需要額外的記憶體空間來輔助排序的進行，因此插入排序演算法也是一個就地 (in place) 演算法，其空間複雜度為 O(1)。 * 插入排序演算法(續) * 插入排序演算法(續) 資料已經由小到大排好的情況下為最佳狀況，在這種情況下，所有的mi=0 (1 ≤ i ≤ n?1)，因此我們有M = 2(n?1) = 2n?2 =O(n)。 當資料為反向的由大到小排列時為最差狀況，在這種情況下，m1= 1;m2= 2; …;mn-1 = n ? 1，或者我們寫為mi = i (1 ≤ i ≤ n ? 1)，因此我們有M = n(n-1)/2+2(n ? 1)=O(n2)。 * 插入排序演算法(續) * 氣泡排序與插入排序演算法比較 * The End * * * * * * * * * * * * * Definiteness: each instruction is clear and unambiguous. To compute “add 6 or 7 to x” is not definite. Finiteness: (the number of steps should be finite and the execution of the steps should terminate) if we trace out the instructions of an algorithm, then for all cases, the algorithm terminates after a finite number of steps. Finiteness implies termination (OS is thus not an algorithm) Effectiveness: All operations should be feasible. Each step must be such that it can, at least in principle, be done by a person using pencil and paper in a finite amount of time. * Definiteness: each instruction is clear and unambiguous. To compute “add 6 or 7 to x” is not definite. Finiteness: (the number of steps should be finite and the execution of the steps should terminate) if we trace out the instructions of an algorithm, then for all cases, the algorithm terminates after a finite number of steps. Finiteness implies termination (OS is thus not an algorithm) Effectiveness: All operations should be feasible. Each step must be such that it can, at least in principle, be done by a person using pencil and paper in a finite amount of time. * Definiteness: each instruction is clear and unambiguous. To compute “add 6 or 7 to x” is not definite. Finiteness: (the number of steps should be finite and the execution of the steps should terminate) if we trace out the ins