塩浦昭義 情報科学研究科 ... - dais.is.tohoku.ac.jp

1 2 (SORTING ALGORITHMS) time complexity (input size) 0 1 log2 0 log2 1 n 1 ,2,.., log2 1 log2 (order notation) n0c n (worst case time complexity) (average time complexity (polynomial) (log n, n2, n5.))

2 (exponential) (2n, n!, nn,..) Sorting 1 2 n (array) n Algorithms for Sorting O(n2) O(n log n) O(n log n) O(n2), Behavior of Bubble Sort A[7] A[8] A[7] > A[8] 2 A[i] = i (i = 1, 2.)

3 , n) A[6] A[7] A[6] > A[7] 2 A[1], .., A[8] A[2], ..,A[8] A[2], .., A[8] A[3], ..,A[8] A[3], .., A[8] Time Complexity of Bubble Sort A[n-1] A[n] A[n-2] A[n-1] A[1] A[2] c (n-1) c c n 2) c n 3) 2 k :c n k) c {(n-1) + (n-2) + +2+1+0} = c(n-1)(n-2)/2 = O(n2) O(n2) Idea of Merge Sort.

4 (divide-and-conquer method) 2 2 Behavior of Merge Sort 2 2 2 Merge of Sorted Sequences B BA1A2A1 A2 B BA1A2 A1 A2 B BA1A22 > 1 BA1A2

5 N1= A1 n2= A2 A1 A2 B c BA1A2 c (n1+n2) Time Complexity of Merge SortT(n) = n n 2 2 c n 2 T(n/2) 2 c n T(n) = n T(n) = 2 T(n/2) + (c+c ) n T(n) = (c+c ) n log2n = O(n log n) n 2 O(n log n) Idea of Quick Sort A[1], .., A[n] , pivot 2 = 3 Behavior of Quick Sort = 3 = 1 = 4 = = = How to Choose Pivot = 3 = = a)

6 = 3 c A[1], A[2] = 3 A[1]=A[2] A[3] = 3 T(n) = n k n k (1 < k < n) T(n) T(k) + T(n k) + c n (c: T(n) 2c n2 O(n2) O(n log n) O(n log n) 5 27, 17, 3, 16, 13, 10, 1, 5)