#1 id:motemen August 27, 2008
id:motemen
1-3
1-5 6-9 10-14 1 2
: n < a 1, a 2,..., a n > a 1 a 2 a n < a 1, a 2,..., a n >
: Google: insertion sort site:youtube.com 1
: procedure Insertion-Sort(A) for j 2 to length[a] do key A[j] i j 1 while i > 0 and A[i] > key do A[i + 1] A[i] i i 1 A[i + 1] key 1 length[a] JS Ruby A.length ( )
: 1 n n + 1
: 1 n n + 1
3
3 : for A[1..j 1]
3 A[1..j 1] A[1] : for A[1..j 1]
3 A[1..j 1] A[1] A[j] OK (while ) : for A[1..j 1]
3 A[1..j 1] A[1] A[j] OK (while ) A[1..j 1] A : for A[1..j 1]
3 A[1..j 1] A[1] A[j] OK (while ) A[1..j 1] A : for A[1..j 1]
T (n)
Insertion-Sort (n = length[a]) for j 2 to length[a] n do key A[j] n 1 i j 1 n 1 while i > 0 and A[i] > key n j=2 t j do A[i + 1] A[i] n j=2 (t j 1) i i 1 n j=2 (t j 1) A[i + 1] key n 1 t j ( ) 1
Insertion-Sort
Insertion-Sort ( ) while 1 : t j = 1 T (n) = an + b
Insertion-Sort ( ) while 1 : t j = 1 T (n) = an + b ( ) while i = 0 : t j = j T (n) = an 2 + bn + c
( )
( ) T (n) = an 2 + bn + c T (n) = an + b
( ) T (n) = an 2 + bn + c = Θ(n 2 ) T (n) = an + b = Θ(n)
( ) T (n) = an 2 + bn + c = Θ(n 2 ) T (n) = an + b = Θ(n) Θ
2 : 2 Google: merge sort site:youtube.com (divide-and-conquer) (incremental approach)
3
1
2 1
2 1 2 : Θ(n)
2 1 2 : Θ(n) ( )
( ) procedure Merge(A, p, q, r) n 1 q p + 1 n 2 r q for i 1 to n 1 do L[i] A[p + i 1] for j 1 to n 2 do R[j] A[q + j] L[n 1 + 1] R[n 2 + 1] i 1 j 1 for k p to r do if L[i] R[j] then A[k] L[i] i i + 1 else A[k] R[j] j j + 1
Merge A[p..k 1] L R k p L[i] R[j] L R A
Merge-Sort(A, p, r) Merge A[p..r]
Merge-Sort(A, p, r) Merge A[p..r] p r (0 1 )
Merge-Sort(A, p, r) Merge A[p..r] p r (0 1 ) : n/2 A[p..q] n/2 A[q + 1..r]
( ) A p r procedure Merge-Sort(A, p, r) if p < r then q (p + r)/2 Merge-Sort(A, p, q) Merge-Sort(A, q + 1, r) Merge(A, p, q, r)
T (n) n ( ) T (n) = Θ(1) a 1/b T (n) = at (n/b) + D(n) + C(n) D(n): C(n):
n/2 D(n) = Θ(1) 2 1/2 a = b = 2, 2T (n/2) Merge Θ(n) C(n) = Θ(n) T (n) = { Θ(1) if n = 1 2T (n/2) + Θ(1) + Θ(n) if n > 1
T(n)
T(n) T (n) = 2T (n/2) + cn
cn T(n/2) T(n/2)
cn T(n/2) T(n/2) T (n/2) = 2T (n/4) + cn/2
cn cn/2 cn/2 T(n/4) T(n/4) T(n/4) T(n/4)
cn cn/2 cn/2 T(n/4) T(n/4) T(n/4) T(n/4) T (n/4) = 2T (n/8) + cn/4,...
cn cn/2 cn/2 T(n/4) T(n/4) T(n/4) T(n/4) c c c c
cn cn/2 cn/2 cn/2 2 = cn cn/4 cn/4 cn/4 cn/4 cn/4 4 = cn c c c c c n = cn
cn cn/2 cn/2 cn/2 2 = cn cn/4 cn/4 cn/4 cn/4 cn/4 4 = cn c c c c c n = cn cn, log 2 n T (n) = cn log 2 n
log 2 n 2 log 2 n = n n
log 2 n 2 log 2 n = n n n log 2 256 = 8 log 2 65536 = 16 log 2 4294967296 = 32
log 2 n 2 log 2 n = n n n log 2 256 = 8 log 2 65536 = 16 log 2 4294967296 = 32
T (n) n
T (n) n
T (n) n Θ, O, Ω,...
Θ- f(n) = Θ(g(n)) n n 0 0 c 1 g(n) f(n) c 2 g(n) c 1, c 2 n 0 ( ) Θ(n 2 ) Θ(n 2 ) =
O- f(n) = O(g(n)) n n 0 0 f(n) cg(n) c n 0 ( ) O(n 2 )
Ω- f(n) = Ω(g(n)) n n 0 0 cg(n) f(n) c n 0 ( )
o- ω- f(n) = o(g(n)) c > 0 n 0 > 0 n n 0 0 f(n) cg(n) ω
140 120 log(x) vs x vs x 2 vs x 3 vs 2 x 0..5 log(x) x x*x x*x*x 2**x 100 80 60 40 20 0 1 1.5 2 2.5 3 3.5 4 4.5 5
1.2e+06 log(x) vs x vs x 2 vs x 3 vs 2 x 10..20 1e+06 log(x) x x*x x*x*x 2**x 800000 600000 400000 200000 0 6 8 10 12 14 16 18 20
1.2e+06 log(x) vs x vs x 2 vs x 3 vs 2 x 10..20 1e+06 log(x) x x*x x*x*x 2**x 800000 600000 400000 200000 0 6 8 10 12 14 16 18 20
O(n!) >> O(k n ) >> ( ) >> O(n k ) >... O(n 3 ) > O(n 2 ) > O(n log n) > O(n) > O(log n) > O(1)