7장에서는 지금까지 배운 내용을 토대로 현실의 코드 기반에 있을 법한 실용적인 코드 예제의 효율성을 분석한다.
코드 효율성을 알아내는 것이 최적화의 첫 번째 단계다.
더욱이 코드가 빅 오 표기법 관점에서 어떤 카테고리에 해당하는지 알면 애초에 최적화가 정말 필요한지 판단할 수 있다. 예를 들어 O(N²)인 알고리즘은 일반적으로 느린 알고리즘이므로, 최적화할 방법이 있는지 고민해봐야 한다.
const averageOfEvenNumbers = (array) => {
let sum = 0;
let countOfEvenNumbers = 0;
for (let i = 0; i < array.length; i++) {
if (array[i] % 2 === 0) {
sum += array[i];
countOfEvenNumbers += 1;
}
}
return sum / countOfEvenNumbers;
};
데이터 원소 N은 배열 내 항목 수다. 반복문은 원소 N개를 순회하니 알고리즘에는 최소 N단계가 걸린다. 만일 원소가 짝수라면 sum을 수정하고 countOfEvenNumbers를 수정하는 두 단계를 더 거친다.
빅 오는 주로 최악의 시나리오에 초점을 맞춘다. 이 코드에서 최악의 시나리오는 배열의 모든 원소가 짝수일 경우이다. 이 경우 데이터 원소 N개에 알고리즘은 3N 단계가 걸린다.
루프 앞에서 두 변수를 초기화하고 0을 할당한다. 엄밀히 말하면 두 단계이다. 루프 뒤에선 sum / countOfEvenNumbers 나누기를 수행한다. 즉, 총 단계 수는 3N + 3 단계이다.
하지만 빅 오 표기법은 상수를 무시한다고도 했으니 알고리즘을 O(3N+3)이 아닌 O(N)이라 부른다.
문자 배열로부터 두 글자짜리 모든 문자열 조합을 모으는 알고리즘이다. ["a", "b", "c", "d"]가 주어지면 ["ab", "ac" ,"ad", "ba", "bc", "bd", "ca", "cb", "cd", "da", "db", "dc"]를 반환한다.
const wordBuilder = (array) => {
let collection = [];
for (let i = 0; i < array.length; i++) {
for (let j = 0; j < array.length; j++) {
if(array[i] !== array[j]) {
collection.push(array[i] + array[j]);
}
}
}
return collection;
}
루프에 또 다른 루프 즉, 반복문 안에 또 다른 반복문으로 중첩해서 실행한다. 바깥 루프는 인덱스 i로 배열의 매 문자를 순회한다. 안쪽 루프 내부에서는 각 인덱스 i에 대해 같은 배열의 매 문자를 인덱스 j로 다시 한 번 순회한다. 안쪽 반복문 내부에선 i와 j에 있는 문자를 이어 붙이되, 같은 인덱스를 가리킨다면 제외한다.
또 다시 데이터 원소 N개가 무엇인지 알아내야 한다. 앞선 예제처럼 N은 함수로 전달된 배열 내 항목 수다.
N개 원소 당 N개 원소를 모두 순회하니 N²단계가 걸린다. 대표적인 O(N²)의 경우이며 중첩 반복문 알고리즘이 대부분 O(N²)이다.
만일 세 글자짜리 모든 문자열 조합을 계산하도록 알고리즘을 수정하면 삼중 중첩 반복문을 사용해야 할 것이며, O(N³)이 될 것이다.
배열의 맨 앞, 가운데, 맨 뒤 값을 가져오는 알고리즘이다.