알고리즘의 복잡도를 측정하기 위한 표기법
일반적인 표기법
- O(1): 입력 공간에 대해 연산 수행 횟수가 변하지 않는 알고리즘
상수 시간
- O(n) 입력 공간에 대해 최대 n번의 연산을 수행해야 하는 알고리즘
선형 시간. ex) 일반적인 반복문
- O(n^2), O(n^3) 최대 n^2, n^3 번의 연산을 수행 해야하는 알고리즘
ex) 중첩 반복문
- O(logn) 로그 시간 복잡도를 가지는 알고리즘
시간 복잡도 O(1) < O(logn) < O(n^2) < O(n^3)
시간 복잡도 계산
- 계수 법칙: 상수 k > 0, f(n) = O(g(n)) 이면 k(f(n)) = O(g(n))
- 합의 법칙: f(n) = O(h(n)), g(n) = O(p(n)) -> f(n)+g(n) = O(h(n)+p(n))
- 곱의 법칙: f(n) = O(h(n)), g(n) = O(p(n)) -> f(n) * g(n) = O(h(n) * p(n))
- 전이 법칙: f(n) = O(g(n)), g(n) = O(h(n)) -> f(n) = O(h(n))
- 다항 법칙: f(n) = k차 다항식 -> f(n) = O(n^k)
참고 사이트: https://www.bigocheatsheet.com/
참고 서적: 자바스크립트로 하는 알고리즘 (배세민 저/김우향 역, 2019)
