[코딩, 처음입니다] Big O와 Big Ω, 알고리즘 실행시간 표기법

 

Big O와 Big Ω

알고리즘 실행시간 표기법

 

---

모두를 위한 컴퓨터 과학 (CS50 2019), David J. Malan (데이비드 J. 말란), Boostcourse

알고리즘에 있어서 대략적으로 실행시간을 알고자할 때, Big O와 Big Ω로 이야기합니다. 예를들어 봅시다. 숫자가 10000까지 무작위로 나열되어있는 집합에서 4543이라는 숫자를 찾으려면 얼마나 걸릴까요? 운이 좋으면 한번에 찾을 수도 있고, 최악의 경우 10000번째에 찾을 수 있습니다. 이때 우리는 big O가 10000이고, big omega가 1이라고합니다. 우리는 이 숫자를 n으로 바꿔서 말합니다. 하나하나씩 찾는 선형겁색은, O(n)이되고 Ω(1)이됩니다. 여기서 O는 “on the order of”의 약자로, 쉽게 생각하면 “~만큼의 정도로 커지는” 것이라고 볼 수 있습니다. O(n) 은 n만큼 커지는 것이므로 n이 늘어날수록 선형적으로 증가하게 됩니다. O(n/2)도 결국 n이 매우 커지면 1/2은 큰 의미가 없어지므로 O(n)이라고 볼 수 있습니다.

 

 

선형검색

8개의 아무숫자를 입력하고 배열에 넣은 뒤에 50이라는 숫자를 검색했습니다. i가 하나씩 커지면서 각 배열을 하나씩 보는 알고리즘입니다. 총 8회를 검색한 뒤에 Not Found라는 문자열을 출력합니다. 이 것이 선형겁색입니다.

만약 정렬되어있다면 어떨까요? 차례대로 정렬되어있다고하면, 하나씩 찾지 않고 중간값을 뽑은뒤에 큰값을 뽑을지 작은값을 뽑을지 결정할 수 있습니다. 그럼 선택할 수는 반이됩니다. 이것이 이진검색입니다.

그럼 정렬을 하는 알고리즘은 뭐가있는지 알아보겠습니다.

 

 

버블정렬

첫번째는 버블정렬입니다. 인접한 자료값을 비교하면서 위치를 교환합니다. www.geeksforgeeks.org/bubble-sort/에 올라온 글을 가지고 알아보겠습니다.

First Pass:
( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ), 여기서 첫번째와 두번째를 비교하면 1보다 5가 더 크니까 5를 뒤로 옮깁니다.
( 1 5 4 2 8 ) –>  ( 1 4 5 2 8 ), 5가 4보다 크니까 바꾸고
( 1 4 5 2 8 ) –>  ( 1 4 2 5 8 ), 5가 2보다 크니까 바꿉니다.
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ), 8이 5보다 크니까 가만히 있습니다. 첫번째는 이렇게 끝납니다.

Second Pass:
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ) 지나가고
( 1 4 2 5 8 ) –> ( 1 2 4 5 8 ) 4가 2보다 크네요 ! 바꿔줍니다.
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) 지나가고
( 1 2 4 5 8 ) –>  ( 1 2 4 5 8 ) 지나갑니다.

이미 정렬되었지만 알고리즘은 알지못합니다. 마지막 바퀴를 돌려줍니다.

Third Pass:
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )

큰 수가 마치 떠오르듯이 뒤로 가게되죠? 그래서 버블 정렬이라고 합니다. 

확인한 갯수는 각 회당 4번이었고(5-1), 총 3차를 돌렸습니다(5-2)이를 식으로 표현하면

(n−1)∗(n−2) = n​2​​−3n+2 이 됩니다.

실행시간의 상한은 O(n^2)라고할 수 있겠죠? 하지만 정렬여부와 관계없이 여전히 확인해야하니 하한

Ω(n^2)가 됩니다. 이 방법이 최선일까요?  이번에는 다른 정렬 알고리즘인 선택 정렬을 배워보겠습니다.

 

선택정렬

역시 숫자가 무작위로 나열되어있습니다. 선택정렬을 하는법은 각 숫자를 확인하고, 가장 작은수를 기억하는 것입니다.

위의 예시와 동일한 숫자를 가지겠습니다.

( 5 1 4 2 8 ) 5를 확인하고, 기억합니다. 두번째로 1을확인하고 1이 더작으니 5를버리고 1을기억합니다. 4를확인하고 1을기억합니다. 2를확인하고 8을 기억합니다. 8을 확인하고 우리는 제일 작은 숫자가 1임을 알 수 있습니다.

( 1 5 4 2 8 ) 우리는 위 과정을 통해 1이라는 것을 알고있고, 배열의 맨 첫번째와 바꿉니다. 이제 두번째로 시작입니다.

5를 확인하고 기억합니다. 두번째로 4를 확인하고 5를 버리고 4를 기억합니다. 2를 확인하고 4를 버리고 2를 기억합니다........ 가장작은 숫자는 2입니다 ! 2와 5를 바꿉니다.

( 1 2 4 5 8 ) 이제 세개의 숫자가남았네요. 위 과정과 똑같이 반복하면됩니다.

어떤가요? 버블정리보다는 교환회수가 줄었지만, 각 자료를 비교하는 횟수는 늘었습니다. 결국 2번의 루프를 돌아야합니다. 상한은 O(n^2)이 됩니다. 하한도 마찬가지로 Ω(n^2) 입니다. 버블 정렬과 동일합니다. 

나쁜 정렬법을 두개나 배웠습니다 ! 박수 !

더 좋은 방법은 뭐가 있을까요?

 

버블정렬을 잠깐만 다시보겠습니다. 만약 정렬되어있는 수였다면 어떨까요? 굳이 바꿀 필요가 없습니다.

1,2,3,4,5,6,7,8,9,10이라는 숫자가 있다고 칩시다. 원래였다면, 각각비교한 뒤에 총 9 * 8번을 비교했겠죠.

하지만 바꿀 필요가 교환이 없을 때 알고리즘을 일찍 종료시킨다면 어떨까요? 그럼 총 9번을 비교하고 알고리즘은 종료될 것입니다. 하한선이 Ω(n^2)에서 Ω(n)이 됩니다 ! 머리를 조금만 쓴다면 실행시간을 대폭으로 줄일 수 있습니다.

 

또 다른 알고리즘은 어떤게 있을까요? 더 좋은 알고리즘이 있을까요? 다음 포스트에서 더 알아보도록 하겠습니다.

 

알고리즘의 실행을 시각적으로 확인할 수 있는 사이트입니다.

www.cs.usfca.edu/~galles/visualization/ComparisonSort.html

Comparison Sorting Visualization

 

실행시간의 상한

• O(n^2): 선택 정렬, 버블 정렬
• O(n log n)
• O(n): 선형 검색
• O(log n): 이진 검색
• O(1)

 

실행시간의 하한

• Ω(n^2): 선택 정렬
• Ω(n log n)
• Ω(n) 버블정렬
• Ω(log n)
• Ω(1): 선형 검색, 이진 검색