Big O | 빅오
자바스크립트로 하는 자료 구조와 알고리즘을 읽고 정리한 것입니다.
빅오 표기법은 알고리즘의 최악의 경우 복잡도를 측정한다.
빅요 표기법에서 n은 입력의 개수를 나타낸다.
빅오 표기법이 해당 알고리즘이 얼마나 효율적인지 나타내기 때문에 중요하다.
빅오 표기법 규칙
계수 법칙 "상수를 제거하라"
입력크기와 연관되지 않는 상수를 전부 무시한다.
빅오에서 입력 크기가 클 때 계수를 무시할 수 있다.
상수 k > 0 인 경우 f(n)이 O(g(n))이면 kf(n)은 O(g(n))이다.
이는 5f(n)과 f(n)이 모두 동일한 O(f(n))이라는 빅오 표기법을 지님을 의미한다.
다음은 시간 복잡도 O(n)을 지닌 코드 이다.
function a(n) {var count = 0;for (var i = 0; i < n; i++) {count += 1;}return count;}