계산복잡도 Computatioal Complexity 계산복잡도개론정렬문제 알고리즘의분석 어떤특정알고리즘의효율 (efficiecy 을측정 시간복잡도 (time complexity 공간복잡도 (space/memory complexity 문제의분석 일반적으로 계산복잡도분석 이란이를지칭 어떤문제에대해서그문제를풀수있는모든알고리즘의효율의하한 (lower-bou 을결정한다. 알고리즘강의슬라이드 7 보기 : 행렬곱셈문제 일반알고리즘 : Θ( 3 Strasse의알고리즘 : Θ(.8 Coppersmith/Wiogra 의알고리즘 : Θ(.38 이문제의복잡도의하한은 Ω( 더빠른알고리즘이존재할까? 아직이하한만큼좋은알고리즘을찾지못하였고, 그렇다고하한이이보다더큰지도알아내지못하였다. 계산복잡도 복잡도하한이 Ω(f( 인문제에대해서복잡도가 Θ(f( 인알고리즘을만들어내는것이목표이다. 다시말하면, 문제의복잡도하한보다낮은알고리즘을만들어낸다는것은불가능하다. ( 물론상수적으로알고리즘을향상시키는것은가능하다. 보기 : 정렬문제 (sortig 교환정렬 (Exchage sort: Θ( 합병정렬 (ergesort: Θ( lg 정렬문제의시간복잡도하한은 Ω( lg ( 키를비교하여정렬하는경우에만해당됨 이정렬문제의경우는하한만큼의시간복잡도를가진알고리즘을찾았다. 알고리즘강의슬라이드 7 3 알고리즘강의슬라이드 7 삽입정렬알고리즘 Isertio Sort 이미정렬된배열에항목을끼워넣음으로서정렬하는알고리즘예 8 7 9 5 3 알고리즘 : 삽입정렬 문제 : 비내림차순을 개의키를정렬 입력 : 양의정수 ; 키의배열 S[..] 출력 : 비내림차순으로정렬된키의배열 S[..] 알고리즘강의슬라이드 7 5 알고리즘강의슬라이드 7 6
삽입정렬알고리즘 voi isertiosort(it, keytype S[]{ iex i,; keytype x; for(i; i<; i++{ x S[i]; i - ; while(>0 && S[]>x{ S[+] S[]; --; S[+] x; 알고리즘강의슬라이드 7 7 삽입정렬알고리즘의분석 최악의경우시간복잡도분석 - 비교하는횟수를기준 : i가주어졌을때, while-루프에서최대한 i-번의비교가이루어진다. 그러면비교하는총횟수는최대한 ( W ( ( i i 평균의경우시간복잡도분석 - 비교하는횟수를기준 : i가주어졌을때, x가삽입될수있는장소가i개있다. 삽입할장소의인덱스 비교횟수 i i x를삽입하는데필요한비교횟수는 : i i ( i i i i + + + L + ( i + ( i k + + i i i i i k i i i i 따라서정렬하는데필요한평균비교횟수는 : i + i + ( + ( ( l i i i i i 공간복잡도분석 : 저장장소가추가로필요하지않다. 따라서 ( Θ(. - 제자리정렬 (i-place sortig 추가로소요되는저장장소의크기가상수인경우. L L i i 알고리즘강의슬라이드 7 8 선택정렬알고리즘 Selectio Sort 문제 : 비내림차순으로 개의키를정렬입력 : 양의정수 ; 키의배열 S[..] 출력 : 비내림차순으로정렬된키의배열 S[..] voi selectiosort(it, keytype S[]{ iex i,,smallest; for(i; i<-; i++{ smallest i; for(i+; <; ++ if(s[]<s[smallest] smallest ; exchage S[i] a S[smallest]; 알고리즘강의슬라이드 7 9 선택정렬알고리즘의분석 모든경우시간복잡도분석 - 비교하는횟수를기준 : i가 일때비교횟수는 -, i가 일때비교횟수는 -,, i 가 - 일때비교횟수는 이 ( 된다. 이를모두합하면, 이다. 따라서 T ( 모든경우시간복잡도분석 - 지정 (assigmet 하는횟수를기준 : 번교환하는데 3번지정하므로 T ( 3( 알고리즘강의슬라이드 7 0 Θ(( 정렬알고리즘의비교 알고리즘 비교횟수 지정횟수 추가저장장소사용량 교환정렬 T( / W( 3 / 제자리정렬 A( 3 / 삽입정렬 W( / W( / 제자리정렬 A( / A( / 선택정렬 T( / T( 3 제자리정렬 삽입정렬은교환정렬보다는항상최소한빠르게수행된다고할수있다. 선택정렬이교환정렬보다빠른가? - 일반적으로는선택정렬알고리즘이빠르다고할수있다. 그러나입력이이미정렬되어있는경우, 선택정렬은지정이이루어지지만교환정렬은지정이이루어지지않으므로교환정렬이빠르다. 선택정렬알고리즘이삽입정렬알고리즘보다빠른가? - 의크기가크고, 키의크기가큰자료구조일때는지정하는시간이많이걸리므로선택정렬알고리즘이더빠르다. 한번비교하는데최대한하나의역을제거하는알고리즘의하한선 개의별개의 ( 다른 키를정렬하는데, 정렬할키들을단순히양의정수,,, 이라고가정해도보편성이희생되지않는다. 개의양수는! 개의순열 (permutatio 이존재한다. 다시말하면,! 가지의다른순서로배열할수있다는뜻이다. k i 를 i번째자리에위치한정수라고할때, 순열은 [k, k,, k ] 으로나타낼수있다. 예를들면, [3,, ] 는 k 3, k, k 3 로표시할수있다. i < 와 k i > k 의조건을만족하는쌍 (pair (k i, k 를순열에존재하는역 (iversio 이라고한다. 예를들어순열 [3,,,, 6, 5] 에는몇개의역이존재할까? 답 : 5개 알고리즘강의슬라이드 7 알고리즘강의슬라이드 7
한번비교하는데최대한하나의역을제거하는알고리즘의하한선 정리 7: 7.: 서로다른 개의키를키끼리비교하여정렬할때, 매번비교할때마다기껏해야하나의역만을제거하는알고리즘은최악의경우에최소한 (( 의비교를수행해야하고평균적으로최소한 ( 의비교를수행해야한다. 알고리즘강의슬라이드 7 3 한번비교하는데최대한하나의역을제거하는알고리즘의하한선 증명 : 경우 : ( 최악의경우 (-/개의역을가진순열이존재한다고보이면충분하다. 왜냐하면그러한순열이있으면알고리즘이그만큼의역을제거해야하고, 따라서최소한그만큼의비교를수행해야하기때문이다. 그러한순열은 :[ [, -,,, ]. 경우 : ( 평균적으로 어떤임의의순열 P [k, k,, k ] 이있을때, 그순열을뒤집어놓으면 (traspose P T [k,, k, k ] 이된다. 이때어떤역이되는쌍 (pair (s, r 은반드시 P에속하거나, 아니면 P T 에속하게된다. 그러면 P와 P T 에는정확하게총 (-/ 개의역이존재하게된다. 따라서 P 와 P T 에존재하는역의평균개수는 (-/이된다. 여기서알고리즘이매번비교할때마다기껏해야하나의역만을제거한다고가정하였으므로, 알고리즘이모든역을제거하기위해서는최소한역의개수만큼의비교를평균적으로수행해야한다. 따라서정렬하는데도그만큼의비교를수행해야한다. 교환, 삽입, 선택정렬은한번비교할때기껏해야하나의역이상은제거할수없으 ( ( 므로시간복잡도가최악의경우, 평균적으로는보다좋을수없다. 알고리즘강의슬라이드 7 합병정렬알고리즘재검토 합병정렬 (ergesort 에서는한번비교해서하나이상의역을제거하는경우가있다. 예를들어, 두부분배열 [3,] 과 [,] 를합병해보자. 3과 을비교한후에 은배열의첫번째자리에놓게되고, 따라서두개의역인 (3, 과 (, 을동시에제거하게된다. 다음, 3과 를비교한후에 는배열의두번째자리에놓게되고, 따라서두개의역인 (3, 와 (, 를동시에제거하게된다. 키를비교하는횟수를기준으로시간복잡도를계산하면 : W ( A( Θ( lg 키를지정하는횟수를기준으로 ( 모든경우 시간복잡도를계산하면 : T ( lg 공간복잡도 : ( Θ( - 제자리정렬이아님. 알고리즘강의슬라이드 7 5 빠른정렬알고리즘재검토 키를비교하는횟수를기준으로시간복잡도를계산하면 : W ( Θ ( a A (.38( + lg 키를지정하는횟수를기준으로 ( 모든경우 시간복잡도를계산하면 : A ( 3 0.69 ( + lg 공간복잡도 : 이알고리즘은합병정렬알고리즘과비교해서추가적인배열이필요하지않는장점이있다. 그러나합병정렬과는달리배열이정확하게반으로나누어지지않으므로, 한쪽의부분배열을정렬할때, 다른한쪽의부분배열의첫번과마지막인덱스를활성레코드 (activatio recor 스택에저장하여둘필요가있다. 따라서추가적으로필요한저장장소는최악의경우 ( Θ ( 가된다. 따라서제자리정렬알고리즘이라고할수없다. 그러나추가적으로필요한저장장소가 ( Θ(lg 가되도록알고리즘수정이가능하다. 알고리즘강의슬라이드 7 6 힙정렬 ( Heapsort 알고리즘 완전이진트리 (complete biary tree: 트리의내부에있는모든마디에두개씩자식마디가있는이진트리. 따라서모든잎의깊이 (epth 는동일하다. 실질적인완전이진트리 (essetially complete biary tree 깊이 -까지는완전이진트리이고, 깊이 의마디는왼쪽끝에서부터채워진이진트리. 힙의성질 (heap pproperty: p 어떤마디에저장된값은그마디의자식마디에저장된값보다크거나같다. 힙 (heap: 힙의성질을만족하는실질적인완전이진트리 보기 알고리즘강의슬라이드 7 7 알고리즘강의슬라이드 7 8
보기 : siftow 알고리즘강의슬라이드 7 9 힙정렬 알고리즘 : 힙정렬 (Heapsort voi siftow(heap& H{ oe paret, largerchil; paret root of H; largerchil paret s chil cotaiig larger key; while(key at paret is smaller tha key at largerchil{ exchage key at paret a key at largerchil; paret largerchil; largerchil paret s chil cotaiig larger key; keytype root(heap& H{ keytype keyout; keyout key at the root; move the key at the bottom oe to the root; elete the bottom oe; siftow(h; retur keyout; 알고리즘강의슬라이드 7 0 보기 : makeheap 알고리즘강의슬라이드 7 힙정렬 voi removekeys(it, heap H, keytype S[]{ iex i; for(i; i>; i-- S[i] root(h; voi makeheap(it, heap& H{ iex i; heap Hsub; for(i-; i>0; i-- for(all subtree Hsub whose roots have epth i siftow(hsub; voi heapsort(it, heap H, keytype S[]{ makeheap(,h; removekeys(,h,s; 알고리즘강의슬라이드 7 힙정렬알고리즘의공간복잡도 이알고리즘이제자리정렬알고리즘인가? 다음과같이힙을배열로구현한경우에는제자리정렬알고리즘이다. 공간복잡도 : Θ( 실질적인완전이진트리를배열로표현하는방법 : 어떤마디를인덱스 i 에넣는다면왼쪽자식마디의인덱스는 i 이다. 어떤마디를인덱스 i 에넣으면오른쪽자식마디는 i+에넣는다. 알고리즘 : 제자리 voi heapsort(it, heap& H{ makeheap(,h; removekeys(,h,h.s; 완전이진트리 배열 알고리즘강의슬라이드 7 3 알고리즘강의슬라이드 7
최악의경우시간복잡도분석 - 비교하는횟수를기준 : 단위연산 : siftow 프로시저에서의키의비교 입력크기 :, 총키의개수 makeheap와 removekeys 모두 siftow을부르므로따로분석을한다. makeheap 의분석 : k 라가정. 를실질적인완전이진트리의깊이라고하면, lg. 이때 의깊이를가진마디는정확히하나이고그마디는 개의조상 (acestor 을가진다. 일단깊이가 인그마디가없다고가정하고키가 sift 되는상한값 (upper bou 을구해보자. epth oe 수 0 0 키가sift되는최대횟수 3 0 알고리즘강의슬라이드 7 5 따라서키가 sift되는총횟수는 ( 를넘지않는다. 이를 0 i + i + 와 i ( + 를이용하여계산해보면, i 0 i 0 ( ( 0 여기에다깊이가 인마디하나가뿌리까지 sift되는횟수 ( 상한값 를더하면, 이된다. 그런데한번 sift될때마다 번씩비교하므로실제비교횟수는 (- 이된다. removekeys 의분석 : k 라가정. 먼저 8이고 lg 8 3인경우를생각해보자. 처음 개의키를제거하는데 sift되는횟수가 회, 다음 개의키를제거하는데 sift되는횟수가 회, 그리고마지막 개의키를제거하는데는 sift 되지않았다. 따라서총 sift 횟수는 ( + ( 3 가된다. 따라서일반적인경우는 0 0 ( + + lg + 가된다. 그런데한번 sift될때마다번씩비교하므로실제비교횟수는 lg + 이된다. 두분석의통합 : 키를비교하는총횟수는 이 k 일때(- + lg - + ( lg - + lg 을넘지않는다. 따라서최악의경우 W( Θ( lg. 일반적으로모든 에대해서도 W( Θ(( ( lg 이라고할수있는데, 왜냐하면 W( 은결국은증가함수 ( 부록B. 이기때문이다. 알고리즘강의슬라이드 7 6 Θ( lg 알고리즘의비교 알고리즘 비교횟수 지정횟수 추가저장장소사용량 합병정렬 W( A( lg T( lg Θ( 빠른정렬 W( / Θ(lg A(.38 lg A( 0.69 lg 힙정렬 W( A( lg W( A( lg 제자리정렬 알고리즘강의슬라이드 7 7 알고리즘강의슬라이드 7 8 키의비교만으로정렬하는경우하한 lg 보다더빠른정렬알고리즘을개발할수있을까? 키의비교횟수를기준으로하는한, 더빠른알고리즘은불가능하다. 정렬알고리즘에대한결정트리 3개의키를정렬하는알고리즘을생각해보자. 그 3개의키를각각 a,b,c 라고한다면다음과같은결정트리 (ecisio tree 를그릴수있다. 알고리즘 : 교환정렬 문제 : 비내림차순으로 개의키를정렬입력 : 양수, 배열 S[..] ] 출력 : 비내림차순으로정렬된배열알고리즘 : voi exchagesort (it, keytype S[] { iex i, ; for (i ; i < -; i++ for ( i+; < ; ++ if (S[] < S[i] exchage S[i] a S[]; 알고리즘강의슬라이드 7 9 알고리즘강의슬라이드 7 30
키의비교만으로정렬하는경우하한 개의키를정렬하기위한결정트리를생각해보자. 만약 개의키의각순열 (permutatio 에대해서, 뿌리마디로부터잎마디로이르는그순열을정렬하는경로가있는경우, 그결정트리는유효하다 (vali 고한다. 즉, 크기가 인어떤입력에대해서도정렬할수있다. 그러면 3개의입력을정렬하는교환정렬알고리즘의결정트리는어떤모양을가질까? 여기서잘살펴보면교환정렬에서는꼭하지않아도될비교를하고있다. 왜냐하면교환정렬에서는어떤시점에서비교가이루어질때, 그이전에이루어졌던비교의결과를전혀알수없기때문이다. 이러한현상은최적 (optimal 이아닌알고리즘에서주로나타난다. 가지친결정트리 (prue ecisio i tree: 일관성있는순서로결정을내림으로서뿌리마디로부터모든잎마디에도달할수있는경우. 다음에있는결정트리는가지친 (prue 결정트리이다. 보조정리 7.: 개의서로다른키를정렬하는결정적 (etermiistic 알고리즘은, 그에상응하는정확하게! 개의잎마디를가진, 유효하며가지친이진결정트리가존재한다. 알고리즘강의슬라이드 7 3 알고리즘강의슬라이드 7 3 최악의경우하한 보조정리 7: 7.: 결정트리에의해서수행된최악의경우비교횟수는그결정트리의깊이와같다. 보조정리 7.3: 이진트리 (biary tree 의잎마디의수가 m이고, 깊이가 이면, lg m 이다. 증명 : 에대하여귀납법으로증명. 우선 m임을먼저보인다. 귀납출발점 : 0: 마디의수가하나인이진트리. 따라서명백히. 귀납가정 : 깊이가 인모든이진트리에대하서, m 가성립한다고가정. 귀납절차 : 깊이가 + 인모든이진트리에대해서, m 임을보이면된다. 여기서 m 은잎마디의수이다. + m 귀납가정에의해서성립 m 각부모다디는기껏해야자식마디 개를가지므로 그러므로 m 이성립한다. 여기서양변에 lg 를씌우면, lg m 이된다. 그런데 는정수이므로, lg m 이된다. 알고리즘강의슬라이드 7 33 최악의경우하한 정리 7.: 개의서로다른키를비교함으로만정렬하는결정적알고리즘은최악의경우최소한 lg - 5.5 번의비교를수행한다. 증명 : 보조정리 7.에의하면,! 개의잎마디를가진가지친, 유효한, 이진결정트리가존재한다. 다시보조정리 7.3에의하면, 그트리의깊이는 lg (! 가되고, 그러면 lg(! lg[ ( ( L ] i lg i lg x x ( l + l lg. 5 따라서보조정리 7.에의해서, 결정트리의최악의경우의비교횟수는그트리의깊이와같다. 증명끝. 알고리즘강의슬라이드 7 3 정렬알고리즘의분류 선택하여정렬하는부류의알고리즘 순서대로항목을선택하여적절한곳에위치시키는알고리즘. 교환정렬, 삽입정렬, 선택정렬, 힙정렬알고리즘이이부류에속한다. 공간복잡도는모두 Θ( ( 이다. 모두제자리정렬알고리즘자리를바꾸어서정렬하는부류의알고리즘 인접해있는항목을교환하여서 ( 자리를바꾸어서 정렬이수행되는알고리즘. 거품정렬 (Bubble Sort(Θ(, 합병정렬, 빠른정렬알고리즘이이부류에속한다. 거품정렬을제외하고는모두제자리정렬알고리즘이아니다. 알고리즘강의슬라이드 7 35 분배에의한정렬 : 기수정렬 키에대해서아무런정보가없는경우에는키들을비교하는것이외에는다른방법이없으므로 Θ( lg 보다더좋은알고리즘을만드는것은불가능하다. 그러나키에대한어느정도의정보를알고있는경우에는상황이조금달라질수있다. 가령키들이음이아닌수이고디지트 (igit 의개수가모두같다면, 첫번째디지트가같은수끼리따로모으고, 그중에서두번째디지트가같은수끼리따로모으고, 마지막디지트가지이런식으로계속모은다면, 각디지트를한번씩만조사를하면정렬을완료할수있다. 다음에예가제시되어있는데, 이런방법으로정렬하는것을 분배에의한정렬 (sortig by istributio - 기수정렬 (raix sort - 이라고한다. 알고리즘강의슬라이드 7 36
보기 - 기수정렬 기수정렬알고리즘 이와같이정렬하는경우항상뭉치 (pile 를구성하는개수가일정하지않으므로관리하기가쉽지않다. 이를해결하기위해서는다음예와같이끝에있는디지트부터먼저조사를시작하면된다. 알고리즘강의슬라이드 7 37 알고리즘강의슬라이드 7 38 기수정렬알고리즘의분석 단위연산 : 뭉치에수를추가하는연산입력크기 : 정렬하는정수의개수, 각정수를이루는디지트의최대개서 umigits 모든경우시간복잡도분석 : T ( umigits ( + 0 Θ( umigits 따라서 umigits가 과같으면, 시간복잡도는 Θ( 가된다. 그러나일반적으로서로다른 개의수가있을때그것을표현하는데필요한디지트의수는 lg 으로볼수있다. 예 : 주민등록번호는 3개의디지트로되어있는데, 표현할수있는개수는 0,000,000,000,000,,, 개이다. 이 0조개의번호를기수정렬하는데걸리는시간은 0,000,000,000,000 log 0 0,000,000,000,000 30조공간복잡도분석 추가적으로필요한공간은키를연결된리스트로만드는데필요한공간, 즉, Θ( 알고리즘강의슬라이드 7 39