시간복잡도(Big-O 표기법)에 관하여

정의

- 컴퓨터(하드웨어) 마다 알고리즘의 속도는 다르기 때문에 "완료까지 걸리는 절차의 수"로 결정된다.
 

 

예시

1. Linear Search

: 데이터를 검색할때 하나씩 검색한다. 따라서 입력의 사이즈가 N이라고 한다면 한번 다 검색하려면 N번 검색해야한다. 이를 O(N) 이라고 한다.

 

 

2. O(1)

def print_first(arr):     print(arr[0])

    > "arr라는 배열에서 첫번째 element를 출력해라"
    > 입력되는 배열의 사이즈가 10이든 100이든 단 1번의 스텝만 필요하다.
    > 이런 경우를 시간 복잡도로 O(1) 이라고 한다.

 

 

3. 또 다른 O(1)

def print_first(arr):       print(arr[0])       print(arr[0])

    > 2번의 Step이 필요. 그렇다고 O(2)라고 하느냐 아니다.
    > 큰 원리에만 관심이 있기 때문에 미리 정해진 숫자에 따라 작동한다.
    > 따라서 이 또한 O(1) 이라고 표현한다.
- 위 두가지 경우를 인풋의 사이즈가 어떻든간에 Constant Time (일정한 시간/상수)로 동작하기 때문에 가능만 하다면 선호되어야할 형태다. 근데 현실은 이렇게 알고리즘이 나오기는 쉽지 않음

 

4. O(n)

def print_all(arr):       for n in arr:           print(n)

    > O(N)

 

 

5. O(n^2)

def print_twice(arr):       for n in arr:           for x in arr:               print(x, n)

    > O(N^2) : 중첩 루프

 

 

 

6. O(log n)

- 이진검색 알고리즘과 같은 경우에서 나오는 로그 시간 복잡도
절반을 나눠서 검색하기 때문에 데이터 사이즈가 2배가 되어도 스텝은 1만 증가함
대신! 정렬되지 않은 배열에는 사용할 수 없다.
    > O(log N)

 

 

 

비교 그래프

시간복잡도 비교 그래프

 

- 가장 선호되는 건 O(1) 상수 시간: 인풋이 늘어나도 변하지 않음
- 그 다음은 O(log N), O(N), O(N^2) 순으로 효율적이다.

 

 

 

 

참고