[🐙알고리즘] 알고리즘 시간 복잡도 개선하기

알고리즘 문제를 풀 때 항상 시간 복잡도가 헷갈려서 정리한다.

빅오 표기법

알고리즘 시간 복잡도는 Big O(빅오) 표기법을 사용한다.
빅오 표기법은 '최악의 상황'을 고려한 표기법이다.

최악의 상황은 갯수가 n인 리스트에서 어떠한 값을 찾는다고 가정했을 때, 마지막 인덱스인 n-1에 해당 값이 위치해 있음을 의미한다.

빅오 표기법을 사용하면 좋은점은 최악의 경우까지 이미 고려를 해둔 셈이기에 최선의 경우를 고려한 빅-오메가 표기법보다 훨씬 연산식을 보고 시간 복잡도를 가늠하기 쉽다는 것이다.

또한 빅오 표기법은 상수값를 제외하고 생각한다.
따라서 n^2+1의 시간이 걸린다고 가정하였을 경우, O(n^2+1)이 아닌 O(n^2)으로 표기한다.

O(1)

O(1)은 상수 시간 알고리즘
입력값의 크기와 상관없이 무조건 1로 가정한다. 따라서 가장 선호되는 알고리즘으로, 가능하다면 상수 시간으로 작성하는 것이 좋다.

O(N)

선형 검색에서 주로 사용되는 시간복잡도이다.

O(N^2)

중첩 반복문이 있을 때 발생한다.

O(NlogN)

이진 검색 알고리즘에서 주로 사용되는 시간복잡도이다.
단, 정렬된 배열에서 사용이 가능하다는 특징이 있다.