알고리즘 복잡도 (빅오표기법)

🔗 알고리즘 복잡도

⏰ 시간복잡도 : 알고리즘의 실행 속도
🏡 공간복잡도 : 알고리즘의 메모리 사이즈

1. 시간복잡도

① 빅오(Big-O)표기법 : 최악의 실행 시간
② 세타(Big-θ)표기법 : 평균 실행 시간
③ 오메가(Big-Ω)표기법 : 최선의 실행 시간

📌 시간복잡도의 순서

O(1) > O(logn) > O(n) > O(nlogn) > O(n^c) > O(c^n) > O(n!)

✔️ O(1)이 가장 좋고, O(n!)이 가장 사용하면 안된다

• O(1) : 입력값에 상관없이 일정한 실행시간의 알고리즘

• O(log n) : 매우 큰 입력값에서도 크게 영향을 받지 않아 이진 탐색 해당

• O(n) : 알고리즘을 수행하는데 걸리는 시간은 입력값에 비례, 선형 시간 알고리즘이라 하며, 정렬되지 않은리스트에서 최대 또는 최솟값을 찾는 경우가 해당되며 모든 입력값을 적어도 한 번 이상은 살펴봐야 한다.

• O (n log n) : 병합 정렬등의 대부분 효율이 좋은 알고리즘이 이에 해당 한다. 아무리 좋은 알고리즘이라 할지라도 n log n 보다 빠를 수 없다. 입력값이 최선일 경우, 비교를 건너 뛰어 O(n)이 될 수 있다.

• O(n^2) : 버블 정렬 같은 비효율적인 정렬 알고리즘 해당

• O(2^n) : 피보나치의 수를 재귀로 계산하는 알고리즘이 이에 해당 한다. n^2와 혼동되는 경우가 있는데 2^n이 훨씬 더 크다.

• O(n!) : 가장 느린 알고리즘으로 입력값이 조금만 커져도 계산이 어렵다.

출처