Big-O Notationの概要

時間の複雑さ

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

Big-O Notation

ㅇO（1）/Constant Time：

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

ㅇO（logn）/Logthmic Time：

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

ㅇO（n）/Liner Time：

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

ㅇO(n^2)/象限時間:

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

ㅇO（2^n）/Exponential Time：

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