빅 오 표기법(big O notation)

 

점근적 표기법(Asymptotic notation)

빅 오 표기법 (big O)	시간의 상한 (최악의 시나리오)    최악의 경우에도 big O를 넘지 않는다.
빅 오메가 표기법 (big Ω)	시간의 하한 (최선의 시나리오)     아무리 빨라도 big Ω보다 빠를 수 없다.
빅 세타 표기법 (big θ)	평균적인 경우 (big O ~ big Ω)

 

빅 오 표기법(big O notation)

 빅 오 표기법은 알고리즘 간 차이를 드러내고 주어진 상황에 알맞은 알고리즘을 결정하게 해주는 훌륭한 도구이다. 빅 오를 사용하면 내가 만든 알고리즘과 세상에 존재하는 범용 알고리즘을 비교할 기회가 생기며 "이 알고리즘이 일반적으로 쓰이는 알고리즘만큼 빠른가 혹은 느린가?"라고 자문해 볼 수 있다.

 

 빅 오 표기법은 알고리즘에 얼마나 많은 단계가 필요한지를 알고리즘이 처리할 데이터 원소 수에 따라 설명한다. 데이터가 증가할수록 단계 수는 어떻게 변하는가?를 알려준다. 

 

 빅 오 표기법은 상수를 무시한다. 빅 오로는 정확히 같은 방법으로 표현되는 두 알고리즘이 있을 때, 한 쪽이 다른 한 쪽보다 100배나 빠를 수 있다는 점 때문에 이 규칙은 빅 오 표기법을 쓸모없게 만드는 것 같지만, 알고리즘의 장기적인 증가율을 분류하는 훌륭한 방법이기에 여전히 매우 중요하다. 어느 정도 크기의 데이터에 대해서는 O(N)이 O(N²)보다 빠르다. O(N)이 O(100N)이든 결과적으로 항상 그렇다.

 

 빅 오 표기법은 상한값(최악의 시나리오)를 다루기 때문에, 두 알고리즘이 같은 분류에 속하더라도 반드시 두 알고리즘의 처리 속도가 같지 않다. 따라서 빅 오에서 다른 분류에 속하는 알고리즘을 대조할 때는 빅 오가 완벽한 도구지만 같은 분류에 속하는 두 알고리즘이라면 어떤 알고리즘이 더 빠를지 알기 위해 더 분석해야 한다.

 

O(1) - 상수시간(constant time)

•데이터가 얼마나 많든 상관없이 알고리즘에 걸리는 단계 수가 항상 일정하다.

•데이터가 아무리 커지더라도 단계 수가 변하지 않는 모든 알고리즘을 표현하는 방법이다.

   (데이터 수 변화에도 단계수가 변하지 않는 것!)

•100단계가 걸리는 것도 O(1)이 될 수 있고, 1단계가 걸리는 것도 O(1)이 될 수 있다.

•100단계가 걸리는 알고리즘이 한 단계 알고리즘보다 덜 효율적이지만 O(1)의 의미는 어떤 O(N) 알고리즘보다도 더 효율적이라는 뜻

예시 - 배열 읽기, 배열 끝에 삽입(push), 삭제(pop)

 

O(N) - 선형시간(linear time)

•N개의 원소가 있을 때 알고리즘을 끝내는데 N개의 단계가 필요하다.

•데이터 원소 수만큼의 단계가 필요하다. 따라서 배열에 원소 하나가 추가되면 알고리즘은 한 단계 늘어난다. 

예시 - 배열 검색(indexOf), 반복문(for), 선형 검색

 

O(logN) - 로그시간(log time)

•데이터가 두 배로 증가할 때마다 한 단계씩 늘어나는 알고리즘을 설명하는 방법이다.

•O(logN)은 사실 O(log₂N)을 줄여 부르는 말이다. 편의를 위해 첨자 2를 생략했을 뿐.

•데이터 원소가 N개 있으면 알고리즘에서 log₂N 단계가 걸린다는 의미.

•log₂8  → 2의 몇 승이 8인가? → 8을 2로 몇 번 나눠야 할까?

•log₂N → 2의 몇 승이 N인가? → N을 2로 몇 번 나눠야 할까?

•원소가 하나가 될 때까지 데이터 원소를 계속해서 반으로 줄이는 만큼의 단계 수가 걸린다는 뜻

•데이터 원소가 두 배로 늘어날 때마다 딱 한 단계만 더 필요하다.

예시 - 이진 검색

 

O(N²) - 이차시간(quadratic time)

•데이터가 늘어날수록 단계 수가 급격히 증가

예시 - 버블 정렬, 중첩 루프

 

 

 

---

참고

책 - 제이 웬그로우〔누구나 자료구조와 알고리즘〕