빅오(O, big-O)
빅오big-O는 알고리즘을 다루는 거의 모든 책에서 상세히 다루는 중요한 주제 중 하나. 빅오는 입력값이 커질 때 알고리즘의 실행 시간(시간복잡도)과 함께 공간 요구사항(공간복잡도)이 어떻게 증가하는지를 분류하는 데 사용. 알고리즘의 효율성 분석에 매우 유용하게 활용됨. ❗️ 입력값이 무한대로 향할때 함수의 상한을 설명하는 수학적 표기 방법이다.
빅오는 점근적 실행시간Asymptotic Running Time을 표기할 때 가장 널리 쓰이는 수학적 표기법 중 하나이다. ❗️ 점근적 실행시간이란 입력값 n이 커질 때, 즉 입력값이 무한대를 향할 때 lim 함수의 실행 시간의 추이를 의미한다. 대상이 되는 것은 입력의 크기가 충분히 클때다.
점근적 실행시간은 달리 말하면 시간 복잡도라 할 수 있다. 시간 복잡도Time Complexity의 사전적 정의는 어떤 알고리즘을 수행하는 데 걸리는 시간을 설명하는 계산복잡도를 의미한다. 계산 복잡도를 표기하는 대표적인 방법이 빅오이다. 빅오로 시간복잡도를 표현할 때는 최고차항만을 표기하며, 상수항은 무시한다.
빅오 표기법의 종류
O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!)
O(1) -> 해시테이블의 조회 및 삽입
입력값이 아무리 커도 실행시간은 일정하다. 최고의 알고리즘. 상수시간을 갖는 알고리즘은 성배와 같아서(ㅎㅎ) 찾을 수만 있다면 놀라운 가치가 있다. 하지만 찾기가 매우매우 힘들다. 상수시간에 실행된다 해도 상수값이 상상을 넘어설 정도로 엄청 크다면 사실상 일정한 시간의 의미가 없다고 본다.
O(log n) -> 이진검색
로그는 매우 큰 입력값에도 크게 영향을 받지 않는 편. 웬만한 n의 크기에 대해서도 매우 견고하다.
O(n)
입력값만큼 실행 시간에 영향을 받으며, 알고리즘을 수행하는 데 걸리는 시간은 입력값에 비례한다. -> 선형 시간Linear-Time알고리즘이라 함
정렬되지 않은 리스트에서 최댓값 or 최솟값 경우가 해당됨. 이 값을 찾기 위해서는 모든 입력값을 적어도 한 번 이상은 살펴봐야 한다.
O(n log n) -> 병합 정렬을 비롯한 대부분의 효율 좋은 정렬 알고리즘
비교 기반 정렬 알고리즘은 아무리 좋은 알고리즘이라도 O(n log n)보다 빠를 수 없다.
O(n^2) -> 버블 정렬 같은 비효율적 정렬 알고리즘
O(2^n) -> 피보나치 수를 재귀로 계산하는 알고리즘
O(n!)
가장 느린 알고리즘. 입력값이 조금만 커져도 웬만한 다항 시간 내에는 계산이 어렵다.
❗️ n^2 에 비해 2^n 은 복잡도가 매우 크므로 서로 혼동하는 일이 없도록 주의! n^2 < 2^n
🟥 알고리즘은 흔히 '시간과 공간이 트레이드오프Space-Time Tradeoff' 관계이다. 실행 시간이 빠른 알고리즘은 공간을 많이 사용하고, 공간을 적게 차지하는 알고리즘은 실행시간이 느리다. 실행 시간이 빠르면서도 공간을 적게 차지하는 알고리즘이 드물지만 존재하긴 한다. 하지만 대부분의 경우 시간과 공간은 트레이드오프 관계이며 이는 알고리즘의 주요한 특징 중 하나이다.
상한과 최악
빅오(O)는 상한을 의미함.
평균적인 시간보다는 상한시간으로 단순화해서 주로 표현. 매번 구분하는 것이 번거롭고 혼동되기도 하며, 상한으로만 표현하는 방법이 틀리지 않기 때문에.
❗️ 빅오 표기법은 '적당히 정확하게' 표현하는 방법. 최악의 경우/평균적인 경우의 시간 복잡도와는 아무런 관계가 없는 개념.
-> 복잡한 함수 f(n)이 있을 경우, 이 중 가장 늦게 실행될 때를 빅오(O), 가장 빨리 실행될 때를 빅오메가(Ω), 평균적으로는 빅세타(⍬)로 지칭. 빅오 표기법은 n이 매우 클 때의 전체적인 큰 그림에 집중한다.
분할 상환 분석
시간 또는 메모리를 분석하는 알고리즘의 복잡도를 계산할 때, 알고리즘 전체를 보지 않고 최악의 경우만을 살펴보는 것은 지나치게 비관적이라는 이유로 분할 상환 분석 방법이 등장하는 계기가 되었다.
빅오와 함께 함수의 동작을 설명할 때 중요한 분석 방법중 하나이다. 유용한 대표적인 예로 '동적배열'이 있다. 최악의 경우를 여러 번에 걸쳐 골고루 나눠주는 형태로 알고리즘의 시간복잡도를 계산할 수 있다.
어떠한 임의의 알고리즘에 대해서, 어떤 연산은 자원적 측면에서 상당한 비용을 소모할 수 있지만, 반면 다른 연산은 그렇게 고비용을 소모하지 않을 수 있다. 분할상환 분석은 알고리즘의 전반적인 연산 집합에 대해 비용이 높은 연산, 그리고 비용이 덜한 연산 모두를 함께 고려하는 기법이라 하겠다. 이것은 다른 종류의 입력, 입력의 길이, 이 알고리즘의 성능에 영향을 미치는 다른 요인들을 전부 고려한다. 수행된 모든 연산에 대해 자료구조 연산만의 어떤 시퀀스를 수행하는데 필요한 시간의 평균을 구한다. 비록 그 시퀀스에서 하나의 연산비용이 비싸더라도, 그 일련의 연산에 대해 평균을 구하면 연산 하나의 평균 비용이 작다는 것을 분할 상환 분석을 이용해 보일 수 있다. 분할 상환 분석은 확률이 포함되지 않으므로 평균비용 분석과는 다르다. 분할 상환 분석은 최악의 경우에도 각 연산의 평균 수행성능을 보장한다.
-위키백과, 우리 모두의 백과사전
병렬화
일부 알고리즘들은 병렬화로 실행 속도를 높일 수 있다. GPU는 병렬 연산을 위한 대표적인 장치이다. GPU 각각의 코어는 CPU보다 훨씬 더 느리지만 GPU의 코어는 수천여 개로 구성되어 있어, 많아봐야 수십여 개에 불과한 CPU보다 수백 배 더 많은 연산을 동시에 수행할 수 있다. GPU는 결국 같은 시간에 목적지에 훨씬 더 많은 짐을 나를 수 있다.
알고리즘 자체의 시간 복잡도 외에도 알고리즘이 병렬화가 가능한지는 근래에 알고리즘의 우수성을 평가하는 매우 중요한 척도 중 하나이다.
<참고문헌>
박상길, '파이썬 알고리즘 인터뷰', 책만, 2020
