Ch.03 빅 오 표기법 (도서 요약 "누구나 자료구조와 알고리즘")
알고리즘의 효율성은 '알고리즘 수행에 필요한 단계 수'이다.
하지만 알고리즘에 필요한 단계 수는 하나로 정할 수가 없다. 선형 검색만 해도 배열의 원소 수만큼 단계가 필요하기 때문에 배열의 크기에 따라 필요한 단계 수가 다르다.
그래서 자료 구조와 알고리즘의 효율성을 간결하고 일관된 언어로 말하기 위해 형식화한 표현이 바로 '빅 오 표기법'이다.
3. 1 빅 오 : 원소가 N개일 때 몇 단계가 필요할까?
최악의 경우 선형 검색에는 배열의 원소 수만큼의 단계가 필요하다. 빅 오 표기법으로 표현하는 방식은 다음과 같다.
O(N)
위 표기는 "데이터 원소가 N개일 때 알고리즘에 몇 단계가 필요한가" 질문에 대한 답을 나타낸다. 그 해답은 빅 오 표현의 괄호 안에 들어있는데, "알고리즘에 N단계가 필요하다"는 의미다. 그래서 O(N)인 알고리즘을 '선형 시간(linear time)을 갖는 알고리즘'이라고 부른다.
만약 일반적인 배열에서 읽기 연산을 진행하면 배열의 크키와 상관없이 딱 한 단계만 필요하다. 이를 빅 오로 표현하면 "데이터 원소가 N개일 때 배열에서 읽기에 몇 단계가 필요할까?"에 대한 답으로 딱 한 단계이다. 따라서 O(1)이라고 표현한다.
어? 원소의 갯수와 무관하게 1이 들어왔다. 이 부분이 핵심이다. 다시 말해 배열에 원소가 몇 개든 배열에서 읽기는 항상 한 단계면 된다. 이러한 이유로 O(1)을 "가장 빠른" 알고리즘 유형으로 분류한다. 데이터가 늘어나도 O(1) 알고리즘의 단계 수는 증가하지 않고, 항상 상수 단계만 필요하다. 그래서 O(1) 알고리즘을 '상수 시간(constant time)을 갖는 알고리즘'이라고도 표현한다.
3. 2 빅 오의 본질
빅 오 표기법은 "데이터 원소가 N개일 때 알고리즘에 몇 단계가 필요한가에 대한 답"이다.
만약에 데이터가 몇 개든 항상 3단계가 걸리는 알고리즘이 있다고 가정하면, 원소가 N개일 때 알고리즘에 항상 3단계가 필요하다. 이를 빅 오로 표현하면? O(3)라고 생각하겠지만 실제로는 O(1)이다. 그 이유는 빅 오의 본질과 관련이 있다.
빅 오가 진정으로 의미하는 것은, 데이터가 늘어날 때 알고리즘의 성능이 어떻게 바뀌는지를 나타내는 것이다. 빅 오는 단순히 알고리즘에 필요한 단계 수만 알려주지 않고, 데이터가 늘어날 때 단계 수가 어떻게 증가하는지를 설명한다!
이런 관점에서 O(1)도, O(3)도 동일한 유형의 알고리즘이다. 아무리 데이터가 증가해도 1단계와 3단계로 처리가 가능하기 때문에 데이터 증가에 영향을 받지 않는 유형이므로 본질적으로 같다. 따라서 O(1)과 O(3)의 차이는 중요하지 않다.
반면 O(N) 알고리즘은 유형이 다르다. 데이터가 늘어날 때 정확히 그 데이터에 비례하여 단계 수가 증가하는 알고리즘 유형으로써 성능에 영향을 미친다. 즉 O(N)은 알고리즘의 효율성과 데이터가 비례 관계에 있음을 알린다.
O(N)은 원소가 하나씩 추가될 때마다 알고리즘이 한 단계씩 더 걸리기 때문에 완벽한 대각선을 그린다. 반면에 O(1)은 데이터가 얼마나 많든 상관없이 완벽한 수평선을 그린다.
그렇다면 항상 100단계가 걸리는 상수 시간 알고리즘이 있다고 가정해보자. 이 O(100) 알고리즘은 O(N) 알고리즘보다 성능이 우수하다고 볼 수 있을까?
원소가 100개 이하인 데이터 세트에서는 O(N) 알고리즘이 O(100) 알고리즘보다 단계 수가 적다. 하지만 원소가 정확히 100개인 지점부터는 O(N) 알고리즘이 더 많은 단계가 걸린다. 특정 구간부터 무한대까지 더 많은 단계가 걸리는 O(N) 알고리즘이 '상수 시간을 갖는 알고리즘'보다 전반적으로 덜 효율적이라고 볼 수 있다. 항상 수백만 단계가 걸리는 O(1) 알고리즘도 마찬가지다. 데이터가 증가할수록 O(N)이 O(1)보다 덜 효율적인 지점에 반드시 다다르게 되기 때문이다.
물론 선형 검색이 항상 O(N)은 아니다. 원하던 항목을 배열의 첫 번째 셀에서 찾았다면 단 한 단계 만에 찾았기 때문에 O(1)이다. 따라서 선형 검색의 효율성을 설명한다면 최선의 시나리오에서는 O(1), 최악의 시나리오에서는 O(N)이라고 할 수 있다.
그러나 일반적으로 빅 오 표기법은 최악의 시나리오를 의미한다. 최악의 시나리오에서 알고리즘이 얼마나 비효율적인지 정확히 아는 것이 더 중요하기 때문이다. 그래서 대부분 O(N)이라고 설명한다.
3. 3 세 번째 유형의 알고리즘
정렬된 배열에서 '이진 검색'은 선형 검색보다 훨씬 빠르다는 사실을 배웠다.
그렇다면 이진 검색을 빅 오 표기법의 관점에서 어떻게 표현할까? 일단 데이터가 커질수록 단계 수가 늘어나므로 O(1)은 아니다. 또한 단계 수가 원소 수보다 훨씬 적으므로 O(N)도 맞지 않다. 예를 들어 이진 검색은 100개의 원소를 포함하는 배열에서 7단계만 걸린다.
빅 오는 이진 검색의 시간 복잡도(효율성)을 다음과 같이 표현한다.
O(log N)
"빅 오 로그 N"이라고 읽는다. 이러한 유형의 알고리즘을 '로그 시간(log time)의 시간 복잡도'라고 한다. 간단히 말해 O(log N) 알고리즘은 "데이터가 두 배 증가할 때마다 한 단계식 늘어남"을 의미한다.
지금까지 배운 세 종류의 알고리즘의 효율성을 정렬하면, O(1) > O(log N) > O(N) 이다.
3. 4 로가리즘
로그(log)는 로가리즘(logarithm)의 줄임말이다. 로가리즘은 지수(exponent)와 반대 관계이다.
2³ 은 2 x 2 x 2 = 8 이라는 뜻이다.
반대로 log₂ 8 의 뜻은 "2를 몇 번 곱해야 8을 얻을 수 있는지"를 뜻한다.
log₂ 64 는 2를 몇 번 곱해야 64를 얻을 수 있는가이다. 더 쉽게 말하면 1이 될 때까지 64를 2로 계속 나눌 때 등식에 얼마나 많은 2가 등장할까에 대한 답이다. 답은 6이다.
3. 5 O(log N) 해석
컴퓨터 과학에서 O(log N)은 편의상 O(log₂ N)을 줄여 부르는 말이다.
O(log N)은 데이터 원소가 N개 일 때 알고리즘에 log₂ N단계가 걸린다는 의미이다. 원소가 8개인 배열이라면 log₂ 8 = 3 이므로 이 알고리즘은 3단계가 걸린다. 원소 갯수가 64개인 O(log 64) 알고리즘이라면? log₂ 64 = 6, 즉 6단계가 필요하다.
간단히 말해 O(log N)은 원소가 하나가 될 때까지 데이터 원소를 계속 반으로 줄이는 만큼의 단계 수가 걸린다는 뜻이다. 이것이 이진 검색이 동작하는 방식이다.
| 원소 개수(N) | O(N) | O(log N) |
| 8 | 8 | 3 |
| 16 | 16 | 4 |
| 32 | 32 | 5 |
| 64 | 64 | 6 |
| 128 | 128 | 7 |
| 256 | 256 | 8 |
| 512 | 512 | 9 |
| 1024 | 1024 | 10 |
3. 6 마무리
빅 오 표기법을 통해 어떤 알고리즘이든 비교할 수 있는 일관된 시스템이 생겼다. 빅 오 표기법으로 실제 쓰이는 시나리오를 분석해서 다양한 자료 구조와 알고리즘 중 사용자의 코드를 더 빠르게 하고 더 큰 부하도 처리할 수 있는 방법을 고를 수 있다.
해당 글은 '누구나 자료구조와 알고리즘' 책의 내용을 기반으로 작성되었습니다.
오로지 학습용으로 작성하였음을 밝힙니다.
더 자세한 내용을 확인하고 싶다면 해당 저서를 참고하시길 바랍니다.