BigO표기법

효율적인 알고리즘을 평가하는 기준은 시간복잡도와 공간복잡도이다.

시간복잡도

입력값의 변화에 따라 연산을 실행할 때 얼마만큼의 시간이 걸리는가이다.

공간복잡도

입력값의 변화에따라 얼마나 많은 공간(space)을 사용하는가이다.

BigO

BigO 표기법은 시간복잡도를 계산할 때 사용하는 표기법으로 오른쪽으로 갈수록 복잡도가 증가한다.
O(1) -> O(log n) -> O(n) -> O(nlogn) -> O(n^2) -> O(n^n) -> O(n!)

기초자료구조의 시간복잡도

배열

[평균]
검색- O(n) 삽입- O(n) 삭제- O(n)
[최악]
검색- O(n) 삽입- O(n) 삭제- O(n)

스택

[평균]
검색- O(n) 삽입- O(1) 삭제- O(1)
[최악]
검색- O(n) 삽입- O(1) 삭제- O(1)

큐

[평균]
검색- O(n) 삽입- O(1) 삭제- O(1)
[최악]
검색- O(n) 삽입- O(1) 삭제- O(1)

연결리스트

[평균]
검색- O(n) 삽입- O(1) 삭제- O(1)
[최악]
검색- O(n) 삽입- O(1) 삭제- O(1)

해시테이블

[평균]
검색- O(1) 삽입- O(1) 삭제- O(1)
[최악]
검색- O(n) 삽입- O(ㅜ) 삭제- O(ㅜ)