4. Big O

Big O : 단계 수 계산

알고리즘의 효율성을 쉽게 분류하고 이해하기 위해서 사용된 표기법

Big O는 시간단위가 아닌 알고리즘에 필요한 단계 수만을 고려한다.

"데이터가 증가할수록 단계 수는 어떻게 변하는가 ?" 라는 질문의 답

 

자료구조에 표기된 Big O는 최악의 시나리오를 바탕으로 표기됨 , 왜?

최악의 시나리오에서 알고리즘이 얼마나 비효율적인지 파악해야

최악을 대비함과 최선의 알고리즘을 선택할 수 있기 때문에 최악의 경우를 표기한다.

 

ex) 보통 배열에서 검색을 할 때, 찾고 싶은 요소가 배열의 맨 앞에 있을 때, Big O는 constant이다.

      하지만 배열의 검색은, 찾고 싶은 요소가 배열의 맨끝에 있다는 시나리오로 표기한다.

 

Big O의 종류

 

1. O(1) 상수시간 [constant time]

데이터 크기와 상관없이 알고리즘에 필요한 단계 수가 일정.

O(1)의 예) 배열의 끝 요소에 대한 추가, 삭제

 

2. O(N) 선형시간 [Linear time]

데이터의 개수와 알고리즘을 끝내는데 걸리는 단계가 같음.

O(N)의 예) 배열의 전체요소 순회

 

3. O(logN) 로그시간 [log time]

데이터가 두 배로 증가할 때마다 한 단계씩 늘어나는 알고리즘.

O(logN)의 예) up down 게임

이진검색은 특정 항목을 찾을 때 정답 수에 도달할 때까지 계속해서 경우의 수를 반으로 나누어 범위를 좁힌다.

 

로그 시간을 이해하기 위해서는 log를 생각하자

log64 = 6

2를 6번 곱해야 64를 얻을 수 있다.

64를 얻기 위해서 6단계가 필요하다.

(= 64가 1이 될 때까지 2로 몇번 나눠야 할까? // 6번)

1단계 64 / 2 = 32

2단계 32 / 2 = 16

3단계 16 / 2 = 8

4단계 8 / 2 = 4

5단계 4 / 2 = 2

6단계 2 / 2 = 1

 

4. O(N^2) 이차시간 [Qudratic time]

데이터가 두 배로 증가할 때마다 데이터 수의 제곱으로 늘어나는 알고리즘.

O(N^2)의 예) Bubble sort

[3,2,1]이라는 배열이 있을 때, 버블정렬을 이용해 내림차순으로 정렬시키기 위해선 9단계(비교+교환)가 필요.