♟️ 시간복잡도와 공간복잡도
복잡도가 낮을수록 좋은 알고리즘
알고리즘 성능을 평가하기 위한 척도
시간 복잡도: 특정한 크기의 입력에 대해 알고리즘의 수행 시간 분석
공간 복잡도: 특정한 크기의 입력에 대해 알고리즘의 메모리 사용량 분석 (RAM/하드디스크 메모리 등)
시간과 공간은 반비례적 경향이 있는데, 최근 대용량 시스템이 보편화되면서 공간 복잡도보다는 시간 복잡도가 우선
♟️ Big-O, Big-Theta, Big-Omega
Big-O
최악의 경우 계산
Big-Theta
Big-O와 Big-Omega의 공통 부분
평균값을 내기 위해 사용. 정확하지는 않지만 간편함
Big-Omega
최선의 경우 계산. 최적 시나리오
♟️ Big-O를 선호하는 이유
최악의 경우를 고려하여 알고리즘을 짜야지 최악의 경우에 최적의 알고리즘을 목표로 개선할 수 있음
♟️ O(1)은 O(N^2)보다 무조건적으로 빠른가
O(1): constant complexity. 입력값의 크기와 관계없이 즉시 출력값을 얻을 수 있음
O(log n): logarithmtic complexity.
O(N): linear complexity. 입력값이 증가함에 따라 시간 또한 같은 비율로 증가
O(N^2): quadratic complexity. 입력값 증가에 따라 시간이 n의 제곱수의 비율로 증가
O(2^N): exponential complexity. 가장 느린 시간 복잡도
빅오는 최악의 경우의 수를 고려하기 때문에 무조건적으로 빠른 건 아님
참고:
우당탕탕