Download presentation
Presentation is loading. Please wait.
1
조 병 규 Software Quality Lab. 한 국 교 통 대 학 교
search 조 병 규 Software Quality Lab. 한 국 교 통 대 학 교
2
탐색을 예시하는 이유 탐색은 컴퓨터의 작업 중 가장 많이 사용되고 있는 작업 중의 하나인 중요한 문제이며
알고리즘의 개선과 선택의 문제에 대한 좋은 예일 뿐만 아니라 최악의 시간 복잡도와 평균 시간 복잡도에 있어서 최적의 하한 한계를 쉽게 추출할 수 있는 문제들 중의 하나이기 때문
3
순차 탐색에서의 시간 복잡도 int linearSearchClass::linearSearch() {
int position = 1; while((position<=n) && (strcmp(x,List[position].name))) { position++; } if(position > n) position = 0; return position; }; W(n) = max{t(1),t(2), ,t(n)} = t(n) = n B(n) = 1 x가 List의 첫 번째에 존재할 경우
4
순차 탐색에서의 평균 시간 복잡도 n+1 A(n) = ∑ p(Ii)t(Ii) i=1 n
= ∑p(Ii)t(Ii) + p(In+1)t(In+1) i=1 n = ∑ (q/n) i + (1 - q)n n = (q/n) ∑ i + (1 - q)n i=1 = (q/n) (n(n+1)/2) + (1 - q)n = q(n+1)/2+ (1 - q)n x가 존재할 확률이 100%(q=1)인 경우 평균적으로 (1/2)n은 비교하여야 함 x가 존재할 확률이 50%(q=1/2)인 경우 평균적으로 (3/4)n은 비교하여야 함 x가 존재할 확률이 0%(q=0)인 경우 평균적으로 n번 비교하여야 함
5
순서화된 리스트에 대한 탐색 일반적 순차 탐색에 대하여 평균 탐색 시간 - q(n+1)/2 + (1-q)n
순서화된 리스트에 대한 탐색 일반적 순차 탐색에 대하여 평균 탐색 시간 - q(n+1)/2 + (1-q)n - 찾고자 하는 원소가 리스트 내에 반드시 존재할 경우 (1/2)n번 정도의 비교 - 존재할 확률이 50%일 경우 약 (3/4)n번 정도를 비교 리스트가 순차적으로 구성되었을 경우의 개선 방법은? 최악의 경우에 대한 시간 복잡도와 최선의 경우에 대한 시간 복잡도는 순차적으로 구성되어 있지 않을 때와 같음 - 그러나 평균 탐색 시간은 개선할 수 있음
6
순서화된 리스트에 대한 탐색 /*079*/ int linearSearchClass::linearSearch()
/*080*/ { /*081*/ int position = 1; /*082*/ int i; /*083*/ /*084*/ while((position<=n) && (i=strcmp(x,List[position].name))) /*085*/ { /*086*/ if(i>0) position++; /*087*/ else position = n + 1; /*088*/ } /*089*/ if(position > n) position = 0; /*090*/ return position; /*091*/ }; W(n) = max{t(1),t(2), ,t(n)} = t(n) = n B(n) = 1 x가 List의 첫 번째에 존재할 경우
7
순서화된 리스트에 대한 평균 탐색 시간 g1 g2 g3 g4 gn-1 gn gn+1
값1 < 값2 < 값3 < . < 값n-2 < 값n-1 < 값n 값1 값2 값3 . . . 값n-2 값n-1 값n List [1] [2] [3] [n-2] [n-1] [n] g g g g gn gn gn+1 g1 = {a : a < List[1]} gi = {k : List[i-1] < k < List[i] for i = 2,3,4,∙∙∙,n} gn+1 = {z : z > List[n]}
8
순서화된 리스트에 대한 평균 탐색 시간 - x가 List 내에 존재할 확률 : q
- 각 위치에 x가 존재할 확률 : p(i) = 1/n 일 경우 x가 List 내에 존재할 경우의 평균 탐색 시간은 다음과 같음 n n A(n) = ∑ q(1/n)i + ∑ (1-q)(1/(n+1))i + (1-q)(1/(n+1))n i= i=1 n n = q(1/n)∑ i + (1-q)(1/(n+1))∑ i + (1-q)(1/(n+1))n i= i=1 = q(1/n)(n(n+1)/2) + (1-q)(1/(n+1)) )(n(n+1)/2) + (1-q)(1/(n+1))n = q(1/n)(n(n+1)/2) + (1-q)(1/(n+1)) )(n(n+1)/2) + (1-q)(1/(n+1))n = q((n+1)/2) + (1-q)(n/2) + (1-q)(1/(n+1))n
9
순서화된 리스트에 대한 평균 탐색 시간 x가 존재할 확률이 100%(q=1)인 경우 평균적으로 약 (1/2)n은 비교하여야 함
10
순서화된 리스트에 대한 개선된 탐색 리스트가 순차적으로 구성되었을 경우의 개선 방법은? - 최선의 탐색 시간은 같으나
최선의 탐색 시간은 같으나 - 최악의 탐색 시간과 평균 탐색 시간은 개선 가능 - 개선 개념 : 비교 대상(원소)의 간격을 조정 값1 값2 값3 . . . 값n-2 값n-1 값n List [1] [2] [3] [n-2] [n-1] [n]
11
순서화된 리스트에 대한 개선된 탐색 비교 대상 원소 수 S1 = n 일 때 비교 간격을 g1로 설정하여 처리
∘ 첫 번재 : x와 List[g1] 비교하여 찾는 원소가 아니면 ∘ 두 번째 : x와 List[2*g1] 비교하여 찾는 원소가 아니면 ∙ ∙ ∘ i 번째 : x와 List[i*g1] 비교 (i*g1≤n)함 따라서 g1으로 하였을 경우 시간 복잡도(비교수)는 ⌊n/g1⌋ 만약 x < List[i*g1] 이면 List[(i-1)*g1+1] < x < List[i*g1-1] (i=2,3,4,∙∙∙) 일 수 있음 비교 간격을 g2(<g1)로 설정하여 처리하였을 경우 ∘(i-1)*g1+1 < 비교범위 < i*g1-1 이고 ∘비교 대상 원소수 S2 = g1 - 1 이며 ∴ 비교수 = ⌊S2 / g2⌋ 따라서 x < List[i*gj] 이면 - List[(i-1)*gj+1]< x <List[i*gj-1] (i=2,3,4,∙∙∙)일 수 있음 - 비교 간격을 gj+1(<gj)로 설정하여 처리하였을 경우 ∘(i-1)*gj + 1 < 비교범위 < i*gj - 1 이고 ∘비교 대상 원소수 Sj = gj - 1 이며 ∴ 비교수 = ⌊Sj / gj⌋ 그러므로 한 번 비교할 때 마다 대상에서 제외 되는 원소 수는 (i-1)gi이므로 최악의 경우에 대한 시간 복잡도와 평균 시간 복잡도를 개선할 수 있음.
12
(예) 순서화된 리스트에 대한 개선된 탐색 10 20 30 40 50 60 70 80 90 100 list [1] [2]
10 20 30 40 50 60 70 80 90 100 list [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] 찾고자 하는 원소는 값이 75인 경우 (1) 첫 번째 처리 : g1을 4로 설정 - S1 = n(=10) - 1 ≤ 비교범위 ≤ 10 - 비교 i = 1 : x > List[4] i = 2 : x > List[8] ∴ t1(n) = 2 - 최대 비교수 = ⌊10 / 4⌋ = 2 (2) 두 번째 처리 : g2를 2로 설정 - S2 = 3 - 5 ≤ 비교범위 ≤ 7 i = 6 : x < List[6] (i = [(t1 * g1) - g1] + g2) ∴ t2(n) = 1 - 최대 비교수 = ⌊3 / 2⌋ = 1 (3) 세 번째 처리 : g3를 1로 설정 - S3 = 1 - 7 ≤ 비교범위 ≤ 7 i = 7 : x > List[7] (i = [(t1 * g1) - g1 + g2] + [(t2 * g2) - g2] + g3) ∴t3(n) = 1 - 최대 비교수 = ⌊1/1⌋ = 1 ∴ t(n) = t1(n) + t2(n) + t3(n) = = 4
13
이진 탐색 리스트의 원소들이 키 값의 크기 순서대로 일정하게 나열되어 있을 경우 대상 범위(전체, 또는 부분)에 대하여 중앙 위치의 원소들을 검사하여 해당 원소를 찾는 방법 따라서 한 번 비교할 때마다 대상 원소의 수가 반씩이 제외되므로 원소가 크기 순으로 정렬되었을 경우 가장 효율적인 방법 시간 복잡도 최악의 경우에 대한 시간 복잡도 W(n) =⌊lgn⌋+1 평균 시간 복잡도 A(n) = ⌊lgn⌋+(1/2)에 접근
14
이진 탐색 /*079*/ int binarySearchClass::binarySearch(int low, int high)
/*080*/ { /*081*/ int mid; /*082*/ int mask; /*083*/ /*084*/ while(low<=high) /*085*/ { /*086*/ mid = (low + high) / 2; /*087*/ mask = strcmp(x,List[mid].name); /*088*/ if(mask == 0) return mid; /*089*/ else /*090*/ if(mask < 0) high = mid - 1; /*091*/ else low = mid + 1; /*092*/ }; /*093*/ return 0; /*094*/ }
15
이진 탐색의 최악의 경우 시간 복잡도 (1/4) (1) n = 1인 경우 low = 1, high = 1
① x ≠ List(1).name 인 경우 low = 2, high = 1 또는 low = 1, high = 0 ∴ loop는 한 번만 수행됨 ② x = L(1).name 인 경우 return mid; ∴ loop는 한 번만 수행됨 그러므로 x가 존재하든 안 하든 기본연산은 무조건 한 번은 수행됨
16
이진 탐색의 최악의 경우 시간 복잡도 (2/4) (2) n > 1인 경우 ① 첫 번째 처리
- 입력 크기 = n, low = 1, high = n - x ≠ List(⌊(1+n)/2⌋).name일 경우 low = ⌊(1+n)/2⌋ + 1, high = n 또는 low = 1, high = ⌊(1+n)/2⌋ - 1 - 다음번 처리 대상의 크기 Ⓐ n이 짝수인 경우 low가 변하면 n/2, high가 변하면 n/2 - 1 Ⓑ n이 홀수인 경우 양쪽 모두 (n-1)/2 ∴ ⌊n/2⌋개의 원소수가 처리 대상임 ② 두 번째 처리 - 입력의 크기 :⌊n/2⌋ 다음 번 처리 대상의 크기 : ⌊⌊n/2⌋/2⌋ ∴ ⌊n/22⌋ .
17
이진 탐색의 최악의 경우 시간 복잡도 (3/4) ⓘ i 번째 처리 - 입력의 크기 :⌊n/2i-1⌋
- X ≠ L(⌊(1+n)/2⌋).name일 경우 다음 번 처리 대상의 크기 : ⌊n/2i⌋ 그러므로 이진 탐색에서의 최악의 경우에 대한 시간 복잡도 ① W(1) = 1 ② W(n) = 1 + W(⌊n/2⌋), (n > 1에 대하여)
18
이진 탐색의 최악의 경우 시간 복잡도 (4/4) ① W(1) = 1
② W(n) = 1 + W(⌊n/2⌋), (n > 1에 대하여) 여기서 W(n)을 확장해 보면 다음과 같음 W(n) = 1 + W(⌊n/2⌋) = 2 + W(⌊n/22⌋) <=== 1 + (1+W(⌊n/22⌋) = 3 + W(⌊n/23⌋) <=== 2 + (1+W(⌊n/23⌋) = 4 + W(⌊n/24⌋) <=== 3 + (1+W(⌊n/24⌋) ∙ = i + W(⌊n/2i⌋) 위에서 W(⌊n/2⌋)는 순환(재귀) 관계에 있는 것이므로 W(⌊n/2i⌋) = W(1)도 성립 따라서 n / 2i = 1 ⇨ n = 2i ⇨ i = lgn lgn은 정수가 아닐 수 있으므로 ⌊lgn⌋으로 수정하면 W(n) = 1 + ⌊lgn⌋, (n ≥ 1에 대하여)
19
이진 탐색의 평균 시간 복잡도 (1/4) 산출을 위한 정의 ∘ n : 입력 크기
∘ Dn : 고려될 수 있는 문제의 입력 크기 n의 집합 ∘ I : Dn의 원소 ∘ P(I) : ∙입력 I의 발생 확률 ∘ q : x가 List에 있을 확률 ∘ 1 ≤ i ≤ n에 대하여 Ii : x = List[i] 인 모든 키 값들(모든 입력) ∘ 2 ≤ i ≤ n에 대하여 In+i : List[i-1] < x < List[i]인 키 값들로 가정하면 In+1 : x < List[1]인 키 값들 I2n+1 : x > List[n]인 키 값들 ∘ t(Ii) = 입력 Ii상에서 수행된 연산의 수 ∙ x가 가질수 있는 위치의 수 : 2n +1 ∵ x가 List에 존재할 경우의 위치 수 = n x가 List밖에 존재할 경우의 위치 수 = n + 1
20
이진 탐색의 평균 시간 복잡도 (2/4) x가 가질수 있는 위치의 수 : 2n +1
∵ x가 List에 존재할 경우의 위치 수 = n x가 List밖에 존재할 경우의 위치 수 = n + 1 산출을 위한 가정 (1) 1 ≤ i ≤ 2n+1에 대하여 모든 위치(간격 포함)들은 거의 같음 (2) 어떤 정수 k ≥ 1에 대하여 n = 2K - 1 - 두 번째 가정(2)은 기본연산의 수행 수(k)와 입력 크기(n)와의 관계를 나타냄 - k = ⌊lgn⌋ + 1이면 최악의 경우에 대한 시간 복잡도임
21
이진 탐색의 평균 시간 복잡도 (3/4) 1≤t≤k에 대하여 St : 기본 연산을 t번 수행하는 입력 크기
Sk = 2k + n + 1 k A(n) = ∑(1/(2n+1))t St t=1 k = 1/(2n+1)∑ t St t=1 k = 1/(2n+1)[∑ t2t-1 + k(n+1)] t=1 = 1/(2n+1)[∑ t2t2-1 + k(n+1)] k = 1/(2n+1)[(1/2)∑ t2t + k(n+1)] t=1 [참고] k ∑ t2t = (k-1)2k+1+2 t=1 = 1/(2n+1)[(1/2)((k-1)2k+1+2) + k(n+1)] = 1/(2n+1)[((k-1)2k+1) + k(n+1)] = ((k-1)2k+1)/(2n+1) + k(n+1)/(2n+1)
22
이진 탐색의 평균 시간 복잡도 (3/4) n = 2K-1 = ((k-1)2k+1)/(2(2K-1 )+1) + k((2K-1 )+1)/(2(2K-1 )+1) = ((k-1)2k+1)/(2K+1-1 ) + k2K/(2K+1-1 ) = ((k-1)2k+1+ k2K) / (2K+1-1 ) = (k2k-2K+1+k2K) / (2K+1-1 ) = (2k2k-2K+1) / (2K+1-1 ) = ((2k-1)2k+1) / (2K+1-1 ) = ((2k-1)2k+1) / (212K-1 ) ≒ (2k-1) / 2 = k - (1/2) = (⌊lgn⌋+1) – (1/2) ∴ A(n) = ⌊lgn⌋ + 1/2
23
(예) 이진 탐색 10 20 30 40 50 60 70 80 90 100 110 120 130 list [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] 비교수 3 4 2 1 9 이하 11 ~ 19 21 29 31 39 41 49 51 59 61 69 71 79 81 89 91 99 101 109 111 119 121 129 131 이상 g1 g2 g3 g4 g5 g6 g7 g8 g9 g10 g11 g12 g13 g14 [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] 3 4
24
(예) 이진 탐색 list [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13]
(예) 이진 탐색 list [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] 10 20 30 40 50 60 70 80 90 100 110 120 130 [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] g1 g2 g3 g4 g5 g6 g7 g8 g9 g10 g11 g12 g13 g14 9 이하 11 ~ 19 21 29 31 39 41 49 51 59 61 69 71 79 81 89 91 99 101 109 111 119 121 129 131 이상 원소위치(i) 비교 수(t(Ii)) 1 3 2 4 3 2 4 5 6 7 1 8 9 10 11 12 13 원소위치(i) 비교 수(t(Ii)) 14(g1) 3 15(g2) 4 16(g3) 17(g4) 18(g5) 19(g6) 20(g7) 21(g8) 22(g9) 23(g10) 24(g11) 25(g12) 26(g13) 27(g14)
Similar presentations