열혈 자료구조 - 1-2. 알고리즘의 성능 분석 방법(4)

빅-오 표기법

- 전의 글에서 $$T(n) = n^2  + 3,  T(n) = n^2 + 100$$ 라는 시간 복잡도 함수가 있을 때 뒤에 숫자는 생략해도 된다고말함

- 하지만 어떤 수는 생략이 가능하고 어떤 수는 생략이 불가능할까

- 이 생략 여부를 생각하기 전에 시간 복잡도 함수를 보는 관점이 어디에 있는지 판단해야 함

- 시간 복잡도는 최악의 경우를 관점으로 두고 있고 처리해야할 데이터가 많은 경우에 맞추어져 있음

- n이 증가함에 따라 나머지 수는 미비한 영향을 주기 때문에 생략이 가능하고 현명하다고 봄

- 이러한 관점에서 바라보는 표기법을 Big-Oh 표기법이라고 함

- 빅-오는 T(n)에서 실제로 영향력을 끼치는 부분을 가르킴

- $$T(n) = n^2 + 2n + 1$$ 이라는 식이 있을 때 아래의 표처럼 실제 영향을 끼치는 부분만을 표현하여 $$O(n^2)$$로 표현

- 빅-오는 다항식일 경우 최고차항의 차수가 빅-오가 됨

- 대표적인 빅-오

    -> 상수형 빅-오 : 연산 횟수가 데이터 수에 관계 없이 진행되는 복잡도. 몇번 진행되더라도 1로 표현

    -> 로그형 빅-오 : 데이터 증가율에 비해 연산 횟수 증가율이 적은 매우 바람직한 유형

    -> 지수형 빅-오 : 중첩 반복문 내에서 나타나는데 좋지 못한 유형

    -> 지수형에서 로그형까지 내리는 노력을 해야함

 

순차 탐색 알고리즘과 이진 탐색 알고리즘의 빅-오

- 순차 탐색의 시간 복잡도 $$T(n) = n => O(n)$$

- 이진 탐색의 시간 복잡도 $$T(n) = log_2 n + 1 => O(logn)$$

- 두 알고리즘의 성능의 차이