[Algorithm] 빅오(Big-O) 표기법으로 시간 복잡도 나타내기

 빅오 표기법, 개발을 시작한 지 일주일에서 한 달 정도 되었으면 누구나가 들어 보셨을 겁니다. 못 들어 봤더라도 O(n), O(n log n)과 같은 표기들은 분명히 보셨을 겁니다못 보셨어요? 그러면 문과 가세요. 그만큼 개발자들과 떼려야 뗄 수 없는, 마치 수영장과 물, 스키장과 눈(!) 같은 존재가 개발자들과 시간 복잡도입니다. 빅오는 그걸 나타내는 표기 중 하나이고요.

 

 빅오는 상한을 의미합니다. 하한을 의미하는 빅오메가도 있고, 평균을 의미하는 빅세타도 있어요. 그런데 빅오를 쓰는 이유는 상한으로 표기해야지 틀리지 않기 때문이에요. 예를 들어 어떤 프로그램이 1초 안에 돌아가겠다고 예상한다면 0.5초 안에 돌아가든 0.3초 안에 돌아가든 상관이 없습니다. 그런데 0.5초나 0.3초 안에 돌아간다고 예상을 했는데 1초가 걸리면 답이 없죠. 그래서 빅오를 사용하는 겁니다.

 

 그래서 빅오는 어떻게 계산할까요? 다음과 같은 계산 과정을 거칩니다.

 

 1. 상수를 없앤다.

    e.g) O(2n²+3n+5) -> O(2n²+3n)

 2. 최고차항만 남겨둔다.

    e.g) O(2n²+3n) -> O(2n²)

 3. 계수를 없앤다.

    e.g) O(2n²) -> O(n²)

 

 빅오는 이렇게 입력값에 따른 알고리즘의 시간&공간 추이만을 살피게 됩니다. 그래서 이 추이에 따른 빅오 표기법의 종류는 다음과 같습니다.

 

 O(1): 최고의 알고리즘입니다. 정말 최고의 알고리즘입니다. 애초에 상수 시간을 가지는 알고리즘이 좋은 알고리즘이에요누가 여러분에게 상수 복잡도의 알고리즘을 권유한다? 높은 확률로 거짓이니까 무시하셔도 됩니다. 해시 테이블의 조회 및 삽입이 여기에 해당합니다.

 

 O(log n): 정말 좋은 1티어 알고리즘입니다. 고등학교 2학년 수학I을 배우신 분들은 다들 아시겠지만, 로그는 n의 값에 크게 영향을 받지 않습니다. 예를 들어, log 101과 log 999 모두 2.XXX...의 값을 가집니다. log 1001과 log 9999 모두 3.xxxx...의 값을 가집니다. log 10001과 log 99999 모두 4.xxxx...의 값을 가집니다그래서 로그함수 보면 X축에 평행한 직선처럼 보입니다. n의 값에 큰 영향을 받지 않는 모습을 볼 수 있죠. 이진 탐색 알고리즘이 여기에 해당합니다.

 

 O(n): 나쁘지 않은 알고리즘입니다. n번 반복하는 거죠. 중첩되지 않은 반복문이 여기에 해당합니다.

 

 O(n log n): 대부분의 정렬 알고리즘이 여기에 해당합니다. 팀소트가 대표적입니다. 팀소트는 파이썬에서 sorted() 함수에서 사용됩니다.

 

 O(n²): 버블 정렬과 2중 반복문이 여기에 해당합니다. 물론 3중 반복은 O(n³)겠죠.

 

 O(2ⁿ): 최악의 알고리즘입니다.. O(n²)과 비슷해 보이지만 사실은 이게 훨씬 비효율적입니다. 예를 들어 n이 100이면 O(n²)에서는 10000이지만 O(2ⁿ)에서는 1267650600228229401496703205376입니다.

 

 O(n!): 악마의 알고리즘입니다. n이 100만 되어도 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000이라는 값을 가지는 것을 볼 수 있죠.