[알고리즘] 복잡도

알고리즘 복잡도

하나의 문제를 푸는 알고리즘은 다양하게 존재할 수 있다.
여러 알고리즘 중에 어떤 알고리즘이 좋은지는 알고리즘 분석 을 통해 알 수 있다.

알고리즘을 분석하는 기준에는 2가지가 있다.

• 시간 복잡도 : 알고리즘의 실행 속도
• 공간 복잡도 : 알고리즘이 사용하는 메모리 크기
  (참고로 시간/공간 복잡도는 작을수록 좋다!)

알고리즘 성능 표기법

O(빅오) 표기법 : 최악의 실행시간, 가장 많이 사용함
Ω(빅오메가) 표기법 : 최상의 실행시간
θ(빅세타) 표기법 : 평균 실행시간

시간 복잡도 : O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(2^n) < O(n!)

References
잔재미코딩