Big-O

빅오(big-O)

빅오의 사전적 정의는 어떤 알고리즘을 수행하는 데 걸리는 시간을 설명하는 계산 복잡도를 의미한다
빅오로 시간 복잡도를 표시할 때는 최고차항만을 표기하며, 계수는 무시한다
ex) 4n^2 + 3n + 4의 시간 복잡도는 O(n^2)이 된다.

빅오 표기법의 종류

• O(1): 입력값이 아무리 커도 실행 시간은 일정하다. 최고의 알고리즘. 상수 시간을 갖는 알고리즘은 성배와 같아서 찾을 수만 있다면 놀라울 정도로 가치가 있지만, 그 성배를 찾기 위해 일평생을 보내야 할지도 모른다. 대표적으로 해시 테이블의 조회 및 삽입이 이에 해당한다.
  
  
• O(log n): 실행 시간은 입력값에 영향을 받는다. 그러나 로그는 매우 큰 입력값에도 크게 영향을 받지 않는 편으로 웬만한 n의 크기에 대해서도 매우 견고하다. 대표적으로 이진 탐색이 이에 해당한다.
  
  
• O(n): 입력값만큼 실행 시간에 영향을 받으며, 알고리즘을 수행하는 데 걸리는 시간은 입력값에 비례한다. 선형 시간 알고리즘이라고 한다.
  
  
• O(nlog n): 퀵 정렬, 병합 정렬을 비롯한 대부분의 효율 좋은 정렬 알고리즘이 이에 해당한다. 적어도 모든 수에 대해 한 번 이상은 비교해야 하는 비교 기반 정렬 알고리즘은 아무리 좋은 알고리즘도 이보다 빠를 수 없다.
  
  
• O(n^2): 2중으로 중첩된 반복문. 버블 정렬같은 비효율적인 알고리즘이 이에 해당한다.
  
  
• O(n^3): 3중으로 중첩된 반복문.
  
  
• O(2^n): 피보나치 수를 재귀로 계산하는 알고리즘이 이에 해당한다. n^2 보다 2^n이 훨씬 더 크다.
  
  
• O(n!): 가장 느린 알고리즘으로, 입력값이 조금만 커져도 웬만한 시간 내에는 계산이 어렵다.

대부분의 알고리즘은 시간과 공간의 트레이트 오프(space-time tradeoff) 관계이다.
실행 시간이 빠른 알고리즘은 공간을 많이 사용하고, 공간을 적게 차지하는 알고리즘은 실행 시간이 느리다는 뜻이다.

빅오는 상한(upper bound)을 의미한다. 최선/최악/평균이 아니다! 이외에도 하한(lower bound)을 나타내는 빅오메가, 평균을 의미하는 빅세타가 있다. 즉 가장 빨리 실행될 때(하한, 빅오메가), 가장 늦게 실행될 때(상한, 빅오) 평균적으로 실행될 때는 빅세타로 지칭한다.

정리하자면, 빅오 표기법은 주어진(최선/최악/평균) 경우의 수행 시간의 상한을 나타낸다.