Disadvantages: On different machines At different time On different inputs No Standards. Hengfeng Wei (hfweiinju.edu.cn)2-2 The Efficiency of Algorithms March05,202011/43
Disadvantages: ▶ On different machines ▶ At different time ▶ On different inputs No Standards. Hengfeng Wei (hfwei@nju.edu.cn) 2-2 The Efficiency of Algorithms March 05, 2020 11 / 43
We need a uniform model of computation. The RAM(Random Access Machine)Model of Computation RAM Model Pr时re的 Astrustion Opereed R read 1. write j R 3. store Re时se5 loa d j 5 Couafer load c c aid j R。 TTtTT Hengfeng Wei (hfweiinju.edu.cn)2-2 The Efficiency of Algorithms March05,202012/43
We need a uniform model of computation. The RAM (Random Access Machine) Model of Computation Hengfeng Wei (hfwei@nju.edu.cn) 2-2 The Efficiency of Algorithms March 05, 2020 12 / 43
The RAM(Random Access Machine)Model of Computation Each memory access takes constant time. Each "primitive"operation takes constant time. Compound operations should be decomposed. Counting up the number of time units. Hengfeng Wei (hfweiinju.edu.cn)2-2 The Efficiency of Algorithms arch05,202013/43
The RAM (Random Access Machine) Model of Computation ▶ Each memory access takes constant time. ▶ Each “primitive” operation takes constant time. ▶ Compound operations should be decomposed. Counting up the number of time units. Hengfeng Wei (hfwei@nju.edu.cn) 2-2 The Efficiency of Algorithms March 05, 2020 13 / 43
Disadvantages: On different machines At different time On different inputs Counting up the number of time units as a function of the input size in typical cases. Hengfeng Wei (hfweinju.edu.cn)2-2 The Efficiency of Algorithms March05,202014/43
Disadvantages: ▶ On different machines ▶ At different time ▶ On different inputs Counting up the number of time units as a function of the input size in typical cases. Hengfeng Wei (hfwei@nju.edu.cn) 2-2 The Efficiency of Algorithms March 05, 2020 14 / 43
INSERTION-SORT(A) cost times 1 for j 2 to A.length CI n 2 key A[j] C2 n-1 3 /Insert A[j]into the sorted sequence A[1..j-1]. 0 1-1 4 i=j-1 C4 n-1 5 whilei>0 and A[i]key C5 ∑1=24 6 A[i+]=A[] C6 2=2(4-1) 7 i=i-1 C7 ∑=20-) 8 Ali+1]key C8 n-1 T(n)=cn+c2(n-1)+c4(n-1) +es∑专与+c6∑G-1)+c∑-1)+cs(n-1) j=2 j=2 j=2 ..as a function of the input size... Hengfeng Wei (hfweinju.edu.cn)2-2 The Efficiency of Algorithms March05,202015/43
T(n) = c1n + c2(n − 1) + c4(n − 1) + c5 ∑n j=2 tj + c6 ∑n j=2 (tj − 1) + c7 ∑n j=2 (tj − 1) + c8(n − 1) . . . as a function of the input size . . . Hengfeng Wei (hfwei@nju.edu.cn) 2-2 The Efficiency of Algorithms March 05, 2020 15 / 43