시간복잡도와 공간복잡도

코드의 품질을 평가하는 두 가지 기준

코드의 품질을 평가하는 기준은 여러 가지가 있는데, 그중 가독성(Readability)과 확장성(Scalability)이 있습니다.

가독성(Readability)은 협업과 관련되어있습니다. 아직 성능 보다는 빠른 실행력이 중요한 초기 스타트업의 경우 확장성보다 가독성을 우선시 여기는 경우도 있다고 합니다.

확장성(Scalability)는 실제 코드 성능과 관련되어 있습니다. 확장성에 영향을 미치는 요소는 2가지가 있는데 1)시간 복잡도와 2)공간 복잡도입니다.
시간 복잡도는 속도를 말하고, 공간 복잡도는 메모리 사용량을 말합니다. 문제는 시간과 공간 복잡도 모두를 얻을 수 없다는 점입니다. 따라서 비즈니스 상황에 맞게 이 두 요소 사이의 균형을 찾는 것이 중요합니다.

코드 품질 평가 기준
- 가독성
- 확장성(Big O)
    - 시간 복잡도
    - 공간 복잡도

Big O

확장성(Scalability)을 평가하기 위해 BigO 표기법을 사용합니다. 이는 알고리즘 또는 함수가 '얼마나 느려지는가'를 알려줍니다. 위 표를 보시면 BigO 타입에 따라 배열의 Elements들이 증가함에 따라 수행할 수 있는 Operation의 수가 달라지는 것을 알 수 있습니다.

Big O는 Big O Asymptotic Analysis의 약자입니다.

Big O 표기 방식의 종류는 이렇습니다.

• O(1) : constant(상수). 문제 풀이를 위한 수학적 연산이 주어진 입력값에 상관없이 일정하게 시간이 소요되는 경우
• O(log N) : Logarithmic. Binary Search로 정렬할 시
• O(n) : Linear. for, while문으로 traverse할 때
• O(n log(n)) : Log linear. sorting할 경우
• O(n^2) : Quadratic. 이중 루프를 도는 경우
• O(2^n) : Exponential. recursive n 크기 문제 푸는 경우
• O(n!) : Factorial. 루프를 돌면서 다른 루프를 추가하는 경우

Big O cheat sheet 참고 자료입니다.
https://www.bigocheatsheet.com/

BigO 표기 규칙

참고로 BigO 표기법은 단순화하여 표현할 수 있습니다. Big O는 정답이 날카롭게 떨어지는 수학 공식보다는 확장성을 가늠하기 위해 사용하는 도구이기 때문입니다.

const cars = ['Porsche', 'Honda', 'Lexus'];

function race(input) {
  let driver = 'John'; // O(1)
  driver = 'John' + ' Smith'; // O(1)
  let score = 0; // O(1)

  // O(n), Linear time
  for (let i = 0; i < input.length; i++) {
    let hasExperience = true; // O(n)
    score++; // O(n)
  }
  return score; // O(1)
}


// O(1)*4 + O(n)*3
// 4 + 3n
// O(n)

이런 식으로 단순화가 가능합니다. 이러한 규칙들이 있는데 정리하면 이렇습니다.

BigO 표기법의 규칙을 정리하면 이렇습니다.

1. 최악의 상황 가정하기. 반복 할 수 있는 경우의 수가 5-10 사이라면 10으로 한다고 가정해야 합니다
2. 상수는 생략합니다. 1이나 10은 그냥 생략.
3. 간소화 합니다. O(2n)도 O(n)으로 간소화. 결국 둘 다 선형시간이기 때문입니다. 자잘한 것들은 간소화할 수 있습니다. O(x^2 + 3x + 100 + x/2) => O(x^2 + 3x + x/2) => O(x^2 + x/2) => O(x^2)
4. 루프가 이중루프인지 여부를 확인해야 합니다. 이중 루프라면 O(n^2)입니다. 하지만 개별적으로 쓸 경우 2개를 쓰더라도 O(2n)이고 이를 단순화하면 O(n)으로 볼 수 있습니다

시간 복잡도

시간 복잡도는 얼마나 시간이 걸리냐를 의미합니다.

함수에서 시간을 잡아먹는 요소들

• 연산(Operation) : +, -, /, x
• 비교(comparison) : <, >, ==
• 반복문(loop) : for, while
• 외부 함수 콜 : (function())

실제 코드의 예시를 들어보겠습니다.

O(1), Constant time

// O(1), Constant time

const cars = ['Porsche', 'Honda', 'Lexus'];

function getFirstOne(cars) {
  console.log(cars[0])
}

getFirstOne(cars);

인풋값인 cars 배열의 길이가 아무리 길어도 항상 0번째가 리턴됩니다. 인풋값과 무간하게 상수 시간이 소요됩니다.

O(n), Linear Time

// O(n), Linear time

const cars = ['Porsche', 'Honda', 'Lexus'];

function findMyPorsche(array) {
  for (let i = 0; i < array.length; i++) {
    if (array[i] === 'Porsche') {
      console.log('This is mine, bro');
    }
  }
}

findMyPorsche(cars);

배열을 단순 반복문으로 돌기 때문에 O(n)입니다.

O(n^2)

const boxes = ['1', '2', '3', '4', '5'];
const collection = [];

function getAllPairs(array) {
  for (let i = 0; i < array.length; i++) {
    for (let j = 0; j < array.length; j++) {
      collection.push([boxes[i], boxes[j]])
    }
  }
  return collection;
}

console.log(getAllPairs(boxes))

공간 복잡도

공간 복잡도는 이 코드가 얼마나 메모리를 사용하고 있냐를 알려줍니다.

공간 복잡도과 관련해서 알아둘 것은

• Heap
• Stack

공간을 잡아먹는 요소는 이렇습니다.

• 변수(variables)
• 데이터 구조(Data structure)
• 함수 호출(Function call)
• 메모리 할당(Allocation)

O(1)

// 공간 복잡도 O(1) - i 변수 1개
// 시간 복잡도 O(n) - loop

function hello(n) {
  for (let i = 0; i < n.length; i++) {
    console.log('hello!')
  }
}

hello([1, 2, 3])

Loop에서 우리가 사용한 공간은 변수 i 달랑 한개입니다. 따라서 공간 복잡도는 O(1)입니다.

// O(1)
const array = ['a', 'b', 'c'];

array[0]; // -> O(1)
array[array.length-1]; //array[2] -> O(1)

O(n)

// 공간 복잡도 O(n) - n개
// 시간 복잡도 O(n) - loop

function hello(n) {

  const memory = [];

  for (let i = 0; i < n.length; i++) {
    memory[i] = 'hello'
  }
  console.log(memory);
}

hello([1, 2, 3])

여기서 반복문의 회전 수 만큼 데이터를 생성했기 때문에 O(n)입니다.