조 병 규 Software Quality Lab. 한 국 교 통 대 학 교 search 조 병 규 Software Quality Lab. 한 국 교 통 대 학 교

탐색을 예시하는 이유 탐색은 컴퓨터의 작업 중 가장 많이 사용되고 있는 작업 중의 하나인 중요한 문제이며 알고리즘의 개선과 선택의 문제에 대한 좋은 예일 뿐만 아니라 최악의 시간 복잡도와 평균 시간 복잡도에 있어서 최적의 하한 한계를 쉽게 추출할 수 있는 문제들 중의 하나이기 때문

순차 탐색에서의 시간 복잡도 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의 첫 번째에 존재할 경우

순차 탐색에서의 평균 시간 복잡도 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번 비교하여야 함

순서화된 리스트에 대한 탐색 일반적 순차 탐색에 대하여 평균 탐색 시간 - q(n+1)/2 + (1-q)n 순서화된 리스트에 대한 탐색 일반적 순차 탐색에 대하여 평균 탐색 시간   - q(n+1)/2 + (1-q)n - 찾고자 하는 원소가 리스트 내에 반드시 존재할 경우 (1/2)n번 정도의 비교 - 존재할 확률이 50%일 경우 약 (3/4)n번 정도를 비교 리스트가 순차적으로 구성되었을 경우의 개선 방법은?   - 최악의 경우에 대한 시간 복잡도와 최선의 경우에 대한 시간 복잡도는 순차적으로 구성되어 있지 않을 때와 같음     - 그러나 평균 탐색 시간은 개선할 수 있음

순서화된 리스트에 대한 탐색 /*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의 첫 번째에 존재할 경우

순서화된 리스트에 대한 평균 탐색 시간 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]   g1 g2 g3 g4 gn-1 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]}

순서화된 리스트에 대한 평균 탐색 시간 - 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=1  i=1                n n                         = q(1/n)∑ i  + (1-q)(1/(n+1))∑ i  + (1-q)(1/(n+1))n              i=1 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 

순서화된 리스트에 대한 평균 탐색 시간 x가 존재할 확률이 100%(q=1)인 경우 평균적으로 약 (1/2)n은 비교하여야 함

순서화된 리스트에 대한 개선된 탐색 리스트가 순차적으로 구성되었을 경우의 개선 방법은? - 최선의 탐색 시간은 같으나   - 최선의 탐색 시간은 같으나 - 최악의 탐색 시간과 평균 탐색 시간은 개선 가능 - 개선 개념 : 비교 대상(원소)의 간격을 조정 값1 값2 값3 .      .      . 값n-2 값n-1 값n List [1] [2] [3] [n-2] [n-1] [n]

순서화된 리스트에 대한 개선된 탐색 비교 대상 원소 수 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이므로 최악의 경우에 대한 시간 복잡도와 평균 시간 복잡도를 개선할 수 있음.

(예) 순서화된 리스트에 대한 개선된 탐색 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) = 2 + 1 + 1 = 4

이진 탐색 리스트의 원소들이 키 값의 크기 순서대로 일정하게 나열되어 있을 경우 대상 범위(전체, 또는 부분)에 대하여 중앙 위치의 원소들을 검사하여 해당 원소를 찾는 방법 따라서 한 번 비교할 때마다 대상 원소의 수가 반씩이 제외되므로 원소가 크기 순으로 정렬되었을 경우 가장 효율적인 방법 시간 복잡도 최악의 경우에 대한 시간 복잡도 W(n) =⌊lgn⌋+1 평균 시간 복잡도 A(n) = ⌊lgn⌋+(1/2)에 접근

이진 탐색 /*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*/ }

이진 탐색의 최악의 경우 시간 복잡도 (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가 존재하든 안 하든 기본연산은 무조건 한 번은 수행됨

이진 탐색의 최악의 경우 시간 복잡도 (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⌋ .

이진 탐색의 최악의 경우 시간 복잡도 (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에 대하여)

이진 탐색의 최악의 경우 시간 복잡도 (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에 대하여)

이진 탐색의 평균 시간 복잡도 (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

이진 탐색의 평균 시간 복잡도 (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이면 최악의 경우에 대한 시간 복잡도임

이진 탐색의 평균 시간 복잡도 (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)

이진 탐색의 평균 시간 복잡도 (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

  (예) 이진 탐색   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

(예) 이진 탐색 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)