Big-O Notation 요약

개념만 간략하게 정리해보자!

시간복잡도

• 알고리즘을 구성하는 명령어들이 몇 번이나 실행되는지를 센 결과와
  각 명령어의 실행시간의 관계를 나타낸다.

* 알고리즘의 성능은 '최선', '최악', '평균'으로 나누며
최악의 경우로 알고리즘의 성능을 파악한다.

Big-O Notation

• 시간복잡도를 표기하는 방법 중 하나.
• 실행시간 n을 O(n)으로 표기하는데 Big-O Notation은
  차수가 가장 높은 최고차항만 두고 나머지는 버린다.

ㅇ O(1) / Constant Time :

- 입력자료의 수에 관계없이 일정한 시간을 갖는 알고리즘.
- ex) 배열에서 특정 인덱스 찾기, 해시테이블 탐색/삽입/삭제 등

ㅇ O(log n) / Logarthmic Time :

- 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어든다.
- 데이터양이 많아져도 시간이 조금씩만 늘어난다.
- 주로 커다란 문제를 일정한 크기를 갖는 작은 문제로 쪼갤 때 나타나는 유형.
- ex) Binary Search Tree의 탐색/삽입/삭제

ㅇ O(n) / Linear Time :

- 입력자료의 크기가 n일 경우 n번 만큼의 수행시간을 가진다.
- 데이터 양에 따라 시간이 정비례한다.
- ex) array 탐색/삽입/삭제, Linked-list 탐색

ㅇ O(n^2) / Quadratic Time :

- 데이터양에 따라 걸리는 시간은 제곱에 비례한다.(효율이 좋지 않아 사용을 안함)
- 보통 2중 for loop을 사용하는 경우
- n의 값이 크다면 실행시간은 감당하지 못할 정도로 커진다.
- 문제를 해결하기 위한 단계의 수는 입력값 n의 제곱이다.
- ex) 버블 정렬, 삽입 정렬

ㅇ O(2^n) / Exponential Time :

- n이 하나 증가할 때 마다 걸리는 시간이 배로 증가하는 알고리즘.
- 여러 개의 답이 있고 그 중 가장 좋은 답을 찾는 문제들을 풀 때 가장 간단한 모든 답을 일일이 고려해보는 것.
- ex) n가지의 음식 중 만든다, 안 만든다의 경우 만들 수 있는 답은 2^n가지.