42page

Big-O

April 1st 2019


Big-O

Big-O notation is used to classify algorithms according to how their running time or space requirements grow as the input size grows.

Big O는 우리가 짠 알고리즘이 input size에 비례해 시간 및 공간 복잡도가 증가하는지 나타내는 표기법입니다. Big O는 worst case를 기준으로 하며 알고리즘의 실행 시간 및 공간 활용을 나타냅니다.

코드의 실행 시간은 데이터의 크기, 실행 환경, 컴파일러, 사용언어 등 여러 변수에 따라 달라집니다. 따라서, Big-O 표기법은 코드 실행의 절대적인 시간을 측정하는 것이 아니라 상대적인 측정을 하기 위해 사용합니다.

Big O는 코드 실행 시간에 큰 차이를 가져오는 부분에만 집중한 표기법입니다. 일반적으로 어떠한 코드를 실행했을 때 300밀리초가 걸리든지 또는 330밀리초가 걸리든지 크게 신경쓰지 않을 것입니다. 하지만, 그 차이가 10초라고 하면 효율적인 코드를 사용하려 할 것입니다.

예를 들어, 3x2 + x + 1 이라는 식을 살펴봅시다. 만약 x가 5면 75 + 5 + 1이 됩니다. 첫 번째 항이 가장 큰 비중을 차지하고 나머지는 큰 영향을 미치지 않습니다. 더 큰 수를 넣으면 그 차이가 더 두드러집니다. x가 5,000,000이면 75,000,000,000,000 + 5,000,000 + 1이 됩니다.

따라서, Big O는 비중이 큰 부분에 집중합니다. 3x2 + x + 1의 Big O는 O(n2)가 됩니다. 아래의 알고리즘을 보며 Big O를 살펴봅시다.

O(n) : linear

function crossAdd(input) {
  const answer = [];

  for (let i = 0; i < input.length; i++) {
    const goingUp = input[i];
    const goingDown = input[input.length - 1 - i];

    answer.push(goingUp + goingDown);
  }

  return answer;
}

위 crossAdd 함수를 실행하면 argument로 전달 받은 배열을 한 번 loop 합니다. 따라서, O(n)이 됩니다. O(n)은 알고리즘의 시간복잡도가 input data에 비례해서 증가합니다.

function find(needle, haystack) {
  for (let i = 0; i < haystack.length; i++) {
    if (haystack[i] === neddle) {
      return true;
    }
  }
}

위의 코드도 loop를 한 번 돌기 때문에 O(n) 입니다. 하지만 아래의 코드는 다릅니다.

linear time complexity를 가지고 있는 array method를 예로 들자면, unshift 메소드가 있습니다. 배열의 처음 index에 새로운 요소를 추가하면, 그 뒤의 모든 요소의 index를 변경해야 합니다. 따라서 배열의 길이만큼 시간복잡도가 증가하기 때문에 O(n)이 됩니다.

반면, pop 메소드의 경우 constant 시간복잡도를 가집니다. 이렇게 같은 Array 메서드이지만 메서드 별 시간복잡도가 다르기 때문에, 이를 인지하며 프로그래밍을 하는 것이 중요하다고 합니다.

하지만 Native Method의 경우 브라우저단에서 자체적으로 최적화가되어 실제로는 성능이 더 좋을 것입니다.

O(n2) : quadratic

function makeTuples(input) {
  const answer = [];

  for (let i = 0; i < input.length; i++) {
    for (let j = 0; j < input.length; j++) {
      answer.push(input[i], input, [j]);
    }
  }

  return answer;
}

makeTuples 함수에서 중복된 for 문을 사용하고 있습니다. 따라서, O(n2)이 되고 이것은 연산의 수를 기하급수적으로 증가시킵니다.

O(N2)는 알고리즘의 실행 시간이 input data의 제곱만큼 걸립니다. 일반적으로 중복된 반복문이 사용된 알고리즘의 경우 O(n2)이 됩니다. 3중 4중으로 중복된 반복문의 경우 O(n3), O(n4)가 됩니다. 하지만, 이러한 경우 알고리즘이 잘못된 길로 나아가고 있는지 확인해봐야 할 것입니다.

O(1) : constant

O(1)은 input data의 크기에 상관없이 실행속도가 일정함을 의미합니다. 일반적으로, O(1)이 가장 좋다고 표현을 하는 경우가 많습니다. 하지만, input에 상관없이 실행 속도가 무조건 24시간이 걸린다면 이것도 O(1)으로 표기할 수 있습니다. 따라서, 무조건 좋다는 표현은 상황에 맞게 사용하는 것이 좋을 것 같습니다.

O(logn) : logarithmic

logarithmic은 input size에 비례해 실행 시간이 증가를 하지만, 증가하는 폭은 점점 줄어듭니다. 각 반복문이 진행될 때마다, 원하는 결과를 얻기 위한 검색 범위가 전체 데이터의 반으로 줄어든다면, 이 log(n)에 해당합니다.

logarithmic의 일반적인 예는 binary search tree 구조에서 찾아볼 수 있습니다. 가장 상위 노드에 중앙값을 배치한 BST가 있습니다. 상위 노드의 값과 비교값을 비교한 후, 해당 노드의 값보다 크면 그 노드보다 작은 쪽의 데이터만 검색을 하면 됩니다. 그리도 반대로 작으면, 해당 노드보다 큰 쪽의 데이터만 검색을 합니다. 이 작업이 매 iteration마다 이루어지기 때문에 검색할 데이터의 범위가 연산 후 반으로 줄어듭니다.

만약 정렬이 된 배열에서 특정 숫자를 찾을 때 수식을 정리해 보면 아래와 같습니다.


O(nk) : exponential

O(nk)은 input size가 증가함에 따라, 시간도 증가하고 그 증가 폭 또한 기하급수적으로 증가할 때 사용하는 표기법입니다. 연산이 기하급수적으로 많아지기 때문에, 제 코드가 이 시간복잡도를 가지고 있다면 뭔가 더 나은 방향을 찾아봐야 할 것 같습니다.

위의 내용을 간략히 정리한 표가 있어 참고하면 도움이 될 것 같습니다.


그리고, 일반적으로 배열의 native method는 시간복잡도 계산 시 참고하지 않지만, 무조건적인것은 아닙니다.

© Chanwhe Kim 2019

Handmade with .