O(1)은 신성하다
하미드 티주쉬(Hamid Tizhoosh)
알고리즘을 구현하는 법을 학습하기 전에 알고리즘이 얼마나 효과적인지 분석하는 법을 이해해야 한다
1장에서는 실행 시간과 사용된 메모리 관점에서 알고리즘 구현을 분석하는 방법을 배워본다
O(1)은 입력 공간에 대해 변하지 않는다 => 상수 시간 => 배열에 있는 항목을 인덱스를 사용해 접근
O(n) => 선형 시간 => 최악의 경우에 n번의 연산을 수행
O(n) => 1중 for 문
O(n^2) => 2중 for 문
O(n^3) => 3중 for 문
O(logn) => 2, 4, 8, 16, 32, 64를 출력하는 알고리즘
O(logn) 시간 복잡도를 가진 로직
function exampleLogarithmic(n) {
for (let i = 2; i <= n; i *= 2) {
console.log(i);
}
}
첫 번째 3가지 법칙과 다항 법칙이 가장 일반적으로 사용된다
각 법칙에 대해서 좀더 자세히 알아보자
function a(n) {
let count = 0;
for (let i = 0; i < n; i++) {
count += 1;
}
for (let i = 0; i < 5 * n; i++) {
count += 1;
}
return count;
}
function a(n) {
let count = 0;
for (let i = 0; i < n; i++) {
count += 1;
for (let i = 0; i < 5 * n; i++) {
count += 1;
}
}
return count;
}