※포스트의 모든 내용은 박상길 저자의 "파이썬 알고리즘 인터뷰" 에서 참고한 내용이다.
• 서론
좋은 코드, 좋은 알고리즘은 무엇일까. 또 코드의 효율성은 어떤 기준으로, 어떻게 비교 또는 분석하여 판단할 수 있을까. 보통은 얼마나 그 코드, 알고리즘이 빠르게 작동하는가(실행시간, 시간복잡도), 사용하는 메모리가 적은가(공간 요구사항, 공간복잡도) 등을 고려한다. 다양한 기준이 있지만 가장 대표적인 것은 바로 빅오(Big-O) 이다. 이 빅오 기법은 입력 값이 커짐에 따라 알고리즘의 시간복잡도와 공간복잡도가 어떻게 변하는지를 보는데 사용되며, 알고리즘의 효율성을 분석하는데 유용하고 널리 사용된다.
• 빅오
컴퓨터에서는 데이터의 양이 작을 때의 경우보다는 무수히 많을 때의 경우를 더 중점적으로 고려한다. 빅오(O, Big-O)는 입력되는 데이터가 무한으로 발산할 때, 함수의 상한을 설명하는 수학적 표기법이다. 만약 n개의 입력되는 데이터가 있을 때, 2n²+3n+7번만큼 계산(비교 또는 스왑 등)한다면 빅오 표기법으로 시간 복잡도는 O(n²)이라고 한다. 빅오로 표기할 때에는 최고차항을 제외한 나머지 항과 계수는 고려하지 않는다. 어차피 n값이 무수히 커졌을 때, 그것들의 영향은 미미하기 때문이다. 이처럼 빅오는 실제로 얼마나 계산되는가가 아니라, 입력값이 커졌을 때 실행하는 시간이 어떻게 증가하는가를 나타낸다. 빅오 표기법의 대표적인 종류는 다음과 같다.
• O(1)
입력값의 변화와 상관 없이 실행 시간이 일정하다. 최고의 알고리즘이지만 그만큼 극히 찾기 힘들다. 해시 테이블의 조회 및 삽입이 이에 해당한다.• O(log n)
실행 시간이 입력값에 영향을 받지만 매우 큰 입력값에도 크게 영향을 받지 않는다. 이진 검색이 이에 해당한다.• O(n)
실행시간이 입력값에 비례한다. 이러한 알고리즘을 선형 시간 알고리즘이라고 부른다.• O(n log n)
합병 정렬 같은 대부분의 정렬 알고리즘이 이에 해당하고 효율이 좋은 알고리즘으로 볼 수 있다.• O(n²)
입력값의 제곱에 비례하게 실행 시간이 적용된다. 버블 정렬 같은 비효율적인 정렬 알고리즘이 이에 해당한다.• O(2ⁿ)
위에 나온 O(n²)과 헷갈릴 수 있지만 n²이 2ⁿ보다 훨씬 작다. 따라서 매우 비효율적인 알고리즘으로 분류된다.• O(n!)
가장 느린 알고리즘으로, 입력값의 아주 작은 증가에도 매우 심한 실행 시간 증가가 나타난다.
빅오는 이와 같이 시간 복잡도를 표현하는 데 쓰이는데 공간 복잡도 또한 표현할 수 있다. 또 알고리즘은 시간과 공간의 트레이드오프 관계이므로 이 둘을 적절히 잘 고려해야한다.
• 분할 상환 분석
분할 상황 분석은 어떠한 함수에 대해 빅오로 표기했을 때, 빅오는 알고리즘의 전체가 아니라 최악의 경우만을 살펴보게 되어 지나치게 비관적일 수 있다는 이유로 등장하게 되었다. 이는 최악의 경우를 여러 번에 걸쳐 골고루 나누어주는 형태로 알고리즘의 시간 복잡도를 계산하는 분석이다. 이러한 분석은 최근 들어 시간 복잡도를 분석하는 데 매우 유용하다 평가되어 보편적으로 사용되는 방법이기도 하다.
• 병렬화
최근 트렌드인 딥러닝이 많은 인기를 끌고 있고 이에 따라 병렬화가 크게 주목받고 있는 상황이다. 딥러닝 알고리즘을 비롯한 GPU를 이용한 병렬 연산이 가능한 알고리즘들이 새롭게 평가되고 있다. 따라서 알고리즘 자체의 시간 복잡도 외에도 알고리즘의 병렬화 가능 여부도 새로운 알고리즘의 우수성 판단 척도로 대두되고 있다.
