7장 일상적인 코드 속 빅 오

현실의 코드 기반에 있을 법한 실용적인 코드 예제의 효율성을 분석한다.
코드 효율성을 알아내는 것이 최적화의 첫 단계다.
코드가 빅 오 표기법 관점에서 어떤 카테고리에 해당하는지 알면 최적화가 필요한지 판단할 수 있다. 예를 들어, O(N²)인 알고리즘은 일반적으로 느린 알고리즘이므로, 최적화할 방법이 있는지 고민해봐야 한다.

7.1 짝수의 평균

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)이라 부른다.

7.2 단어 생성기

문자 배열로부터 두 글자짜리 모든 문자열 조합을 모으는 알고리즘이다. ["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에 대해 배열의 모든 문자를 다시 한 번 순회한다. 안쪽 반복문 내부에선 i와 j에 있는 문자를 이어 붙이되, 같은 인덱스를 가리킨다면 제외한다.

데이터 원소 N은 배열 내 항목 수다.
N개 원소 당 N개 원소를 모두 순회하니 N²단계가 걸린다. 대표적인 O(N²)의 경우이며 중첩 반복문 알고리즘이 대부분 O(N²)이다.

만일 세 글자짜리 모든 문자열 조합을 계산하도록 알고리즘을 수정하면 삼중 중첩 반복문을 사용해야 할 것이며, O(N³)이 될 것이다.

7.3 배열 예제

배열의 맨 앞, 가운데, 맨 뒤 값을 가져오는 알고리즘이다.

const sample = (array) => {
  const first = array[0];
  const middle = array[array.length / 2];
  const last = array[array.length - 1];

  return [first, middle, last];
};

데이터 원소 N은 배열 내 항목 수다.
배열의 시작, 중간, 마지막 인덱스 읽기는 배열 크기에 상관 없이 한 단계다.
배열의 길이를 찾고 그것을 반으로 나누는 것 역시 한 단계다.

단계 수가 상수이므로, O(1)인 알고리즘이다.

7.4 평균 섭씨 온도 구하기

도시의 온도를 모아 온도의 평균을 계산한다. 섭씨 값을 반환하지만 입력 값은은 화씨이다.
섭씨 온도 평균을 구하기 위해 알고리즘은 1) 화씨 온도를 섭씨로 변환하고, 2) 섭씨 온도의 평균을 계산한다.

const averageCelsius = (fahrenheitReadings) => {
  const celsiusNumbers = [];
  for (let i = 0; i < fahrenheitReadings.length; i++) {
    const celsiusConversion = (fahrenheitReadings[i] - 32) / 1.8;
    celsiusNumbers.push(celsiusConversion);
  }

  let sum = 0;
  for (let j = 0; j < celsiusNumbers.length; j++) {
    sum += celsiusNumbers[j];
  }

  return sum / celsiusNumbers.length;
};

데이터 원소 N은 fahrenheitReadings의 항목 수다.
첫 번째 반복문은 원소 N개를 돌며 화씨 온도를 섭씨로 변환한다.
두 번째 반복문은 원소 N개를 돌며 섭씨 온도의 합을 구한다.
두 반복문 모두 N 단계가 걸리니 총 2N 단계가 걸린다. O(N)인 알고리즘이다.

N단계 * N단계인 중첩 반복문과는 달리, 나란히 실행하는 반복문은 N단계 + N단계이다.

7.5 의류 상표

새로 생산한 의류 품목 배열을 받아 상표에 넣어야 할 텍스트를 생성한다. 상표에는 1) 품명과 2) 1부터 5까지의 사이즈가 들어가야 한다.

["Purple Shirt", "Green Shirt"]라는 배열을 받았다면, [ 'Purple Shirt Size: 1', 'Purple Shirt Size: 2', 'Purple Shirt Size: 3', 'Purple Shirt Size: 4', 'Purple Shirt Size: 5', 'Green Shirts Size: 1', 'Green Shirts Size: 2', 'Green Shirts Size: 3', 'Green Shirts Size: 4', 'Green Shirts Size: 5' ]라는 배열을 리턴한다.

const markInventory = (clothingItems) => {
  const clothingOptions = [];

  for (let i = 0; i < clothingItems.length; i++) {
    for (let size = 0; size < 5; size++) {
      clothingOptions.push(`${clothingItems[i]} Size: ${size + 1}`);
    }
  }

  return clothingOptions;
};

데이터 원소 N은 clothingItems의 항목 수다.
이 알고리즘은 중첩 반복문이 있으니 O(N²)이라고 생각할 수 있다.
하지만 바깥 반복문이 원소를 순회하며 N번 실행되는 동안, 안쪽 반복문은 매 원소마다 5번 실행된다.
즉 안쪽 반복문은 N이 얼마든 항상 5번 실행된다. 즉, N²번이 아니라 5N번 실행되는 알고리즘이다.

따라서 O(N)인 알고리즘이다.

7.6 1 세기

이 함수는 배열들의 배열을 받는다. 안쪽 배열들은 1과 0으로 이뤄진다. 함수는 배열들에 들어있는 1의 개수를 반환한다.

입력이 [ [ 0, 1, 1, 1, 0 ], [ 0, 1, 0, 1, 0, 1 ], [ 1, 0 ] ]라면, 1의 개수는 7개이므로 7을 반환한다.

const countOnes = (outerArray) => {
  let count = 0;

  for (let innerArray of outerArray) {
    for (let number of innerArray) {
      if (number === 1) {
        count += 1;
      }
    }
  }

  return count;
};

중첩 반복문이 2개이므로 O(N²)으로 결정짓기 쉽다. 하지만 바깥 반복문은 안쪽 배열을 순회하고, 안쪽 반복문은 실제 수를 순회한다.
즉, 안쪽 반복문이 모든 수의 개수만큼만 실행된다.
따라서 데이터 원소 N은 모든 수의 개수이다.
알고리즘에서 데이터 원소 N의 개수만큼의 단계가 실행되니 O(N)인 알고리즘이다.

7.7 팰린드롬 검사기

팰린드롬은 앞으로 읽으나 뒤로 읽으나 똑같은 단어 혹은 구절이다. "racecar", "kayak", "deified" 등이 팰린드롬이다.

const isPalindrome = (string) => {
  let leftIndex = 0;
  let rightIndex = string.length - 1;

  while (leftIndex < string.length / 2) {
    if (string[leftIndex] !== string[rightIndex]) {
      return false;
    }
    leftIndex++;
    rightIndex--;
  }

  return true;
};

데이터 원소 N은 string의 길이이다.
while 반복문 안이 알고리즘의 핵심이다. 문자열 중간에 도달할 때까지만 실행되는 반복문이다.
N/2 단계를 실행하므로 O(N) 이다.

7.8 모든 곱 구하기

수 배열을 받아 모든 두 숫자 조합의 곱을 반환하는 알고리즘이다.
입력이 [1, 2, 3, 4, 5]라면 [2, 3, 4, 5, 6, 8, 10, 12, 15, 20]을 반환한다.
1을 2, 3, 4, 5와 곱하고 2를 3, 4, 5와 곱하고, 3을 4, 5와 곱하고 4와 5를 곱한다.
즉, 각 수는 오른쪽에 남아있는 수만 곱한다.

const twoNumberProducts = (array) => {
  let products = [];

  for (let i = 0; i < array.length - 1; i++) {
    for (let j = i + 1; j < array.length; j++) {
      products.push(array[i] * array[j]);
    }
  }
  
  return products;
};

데이터 원소 N은 배열의 항목 수다.
바깥 반복문은 N번 실행된다. 안쪽 반복문은 바깥 반복문이 실행될 때마다 1단계씩 줄어든다.
N의 관점에서 안쪽 반복문은 N + (N - 1) + (N - 2) + (N - 3) + ... + 1번 실행된다. 이는 N²/2 단계다.
따라서 O(N²)인 알고리즘이다.

7.8.1 여러 데이터 세트 다루기

한 배열의 모든 수와 다른 한 배열의 모든 수의 곱을 계산하면 어떻게 될까?
가령 [1, 2, 3]과 [10, 100, 1000]을 입력하면 [10, 100, 1000, 20, 200, 2000, 30, 300, 3000]을 반환해야 한다.

const twoNumberProducts = (array1, array2) => {
  let products = [];

  for (let i = 0; i < array1.length; i++) {
    for (let j = 0; j < array2.length; j++) {
      products.push(array1[i] * array2[j]);
    }
  }

  return products;
};

데이터 원소 N을 섣불리 결정할 수 없다.
한 배열의 크기를 N, 다른 배열의 크기를 M으로 해서 시간 복잡도를 O(N * M) 으로 표현하는 수밖에 없다.
별개의 두 데이터 세트를 서로 곱해야 할 때 두 데이터 세트를 별개로 구분해야만 빅 오 관점에서 효율성을 나타낼 수 있다.

만일 N = M 이라면 O(N²)과 동등하다.
만일 N > M 이라면 상수를 무시하는 빅 오 표기법 상 O(N)이 된다.
따라서 O(N * M)은 O(N)과 O(N²) 사이 정도로 이해할 수 있다.

7.9 암호 크래커

다음 알고리즘은 주어진 길이의 모든 문자열 조합을 생성한다.

def every_password(n)
  (("a" * n)..("z"*n)).each do |str|
    puts str
  end
end

(자바스크립트로 구현하는 방법을 모르겠다 ㅠㅠ)

가령 n이 3이라면 aaa부터 zzz까지 가능한 모든 문자열을 순회하도록 반복문이 실행된다.

만약 한 글자짜리 조합이라면 26개,
두 글자짜리 조합을 전부 출력하면 26 26개,
세 글자짜리 조합을 전부 출력하면 26 26 * 26개의 조합이 나온다.

즉, 이 알고리즘은 26^N 단계가 걸린다. O(26ⁿ)으로 표기한다.
N이 1씩 늘어날 때마다 단계 수가 26배씩 늘어난다.

7.10 마무리

온갖 종류의 알고리즘을 분석해 시간 복잡도를 분류할 수 잇다. 이러한 지식을 갖췄으니 체계적으로 코드 속도를 최적화할 수 있다.