[Extra] Big-O(빅오 표기법)

Big-O (빅오 표기법)

- 프로그램의 시간 복잡도를 표기하는 방법

- 알고리즘의 성능을 표현하기 위해 사용

빅오 적용법

1. 입력값을 확인하여 무엇을 N 으로 놓을지 정함

2. 알고리즘에서 수행할 연산 횟수를 N의 식으로 표현

3. 차수가 가장 높은 N만 남김

4. 모든 상수인수를 없앰

(ex. O(n^2/2) -> O(n^2))

빅오 성능순서

0. O(1) (성능순서에 제외)

- 상수 실행 시간

- 항상 일정한 시간에 완료 되지만 현실적으로 거의 없는 알고리즘

1. O(log N)

- 로그 알고리즘

- 실행시간이 입력크기의 로그에 비해 늘어남

- 일반적으로 좋은 효율의 알고리즘

2. O(N)

- 선형 알고리즘

- 실행시간이 입력크기에 비례하여 늘어남

3. O(N log N)

- 초선형 알고리즘

- 처리 데이터의 양이 늘 수록 정비례보다 약간 더 실행시간 늘어남

4. O(N^C)

- 다항식 알고리즘

- 입력크기가 늘어날수록 빠르게 실행시간이 늘어남

- 대용량 데이터일수록 처리시간 망함

5. O(C^N)

- 지수 알고리즘

- 다항식 알고리즘보다 느림...

- 데이터가 조금만 늘어나도 망함

6. O(N!)

- 팩토리얼 알고리즘

- 제일 망함

- 5개만 들어와도 5*4*3*2*1

*일반적인 계산이긴 하나 면접 질문일 경우 최선, 평균, 최악 케이스인지 확인하는 것도 좋음