[Algorithm] 시간 복잡도(Time complexity)와 Big-O 표기법

무엇이 좋은 코드(Clean code)인가? 

---

우리가 어떤 코드를 작성할 때, 이 코드가 좋은 코드인지를 판별할 수 있는 기준은 무엇이 있을까요?

누군가 우리에게 와서 좋은 코드를 작성해달라고 부탁한다면, 우리는 어떤 기준에 맞추어서 코드를 작성해야 할까요?

개발자들 사이에서, 좋은 코드를 판별하는 기준은 일반적으로 다음과 같은 두 가지 기준으로 설명합니다.

 

1. Readable (가독성)

• 다른 사람이 봤을 때, 일반적으로 깨끗하고 누구나 우리의 코드를 이해할 수 있는지에 대한 것입니다.

2. Scalable (확장성)

• 내부의 유지 보수가 쉽고 확장가능하며 좋은 생산성과 효율을 가지는 코드에 관한 추상적인 개념입니다.

우리는 Big-O를 이용해서 프로그램을 실행시키는데 걸리는 시간과 그 효율성의 측면에서 확장성에 대한 좀 더 구체적인 아이디어를 얻을 수 있습니다.

 

다시 말해서, Big-O를 통해 어떤 코드가 좋은 코드(Clean code)인지에 대한 하나의 기준을 제공받을 수 있습니다.

 

시간 복잡도(Time complexity)와 Big-O notation

---

어떤 알고리즘이 문제를 해결할 때 걸리는 시간과 입력 사이의 함수 관계를 시간 복잡도라고 합니다.

그리고, 이러한 시간 복잡도를 표기하는 방법 중 가장 대표적인 것이 Big-O 표기법입니다.

Big-O Chart

Big-O는 위와 같이 O(1), O(n), O(log n) ... 등 기호 O와 입력값에 따른 연산의 실행 횟수에 대한 함수 관계를 괄호안에 함께 나타내는 방식으로 표기합니다.

어떤 알고리즘이 어떤 시간복잡도를 가지는지는 내용이 많아서 따로 다른 글에서 다시 다루어보는걸로 하고, 지금부터는 Big-O 표기법의 4가지 Rule에 대해 알아보겠습니다. Big-O는 개발자들 사이에서 일반화된 정해진 표기법을 따라야 합니다.

Rule 1 : Worst case (항상 최악의 경우만 고려한다)

---

const everyone = ['1', '2', '3', '4', 'nemo', '6', '7', '8', '9', '10'];
//const everyone = ['nemo', '2', '3', '4', '5', '6', '7', '8', '9', '10'];
//const everyone = ['1', '2', '3', '4', '5', '6', '7', '8', '9', 'nemo'];

function findNemo1(array) {
  for (let i = 0; i < array.length; i++) {
    if (array[i] === 'nemo') {
      console.log('Found NEMO!');
      break;
    }
  }
}

findNemo1(everyone);

Big-O 표기법은 항상 최악의 경우를 생각합니다. 즉 어떤 프로그램이 실행될 때 소요될 수 있는 최악의 시간을 고려합니다.

예를 들어보겠습니다. 위 코드는 for문에서 nemo를 찾으면 종료되는 코드입니다.

1. 현재 첫번째 everyone 배열에서, nemo는 5번째에 있는 것을 알 수 있습니다. 따라서 위 코드의 for문은 5번을 돌면 nemo를 찾고 break를 통해 종료됩니다. 
2.  그러나 두번째 everyone 배열에서는, nemo는 첫번째에 있습니다. 따라서 위 코드의 for문은 1번만 돌면 nemo를 찾고 종료됩니다. 이때 시간복잡도는 O(1) 입니다.
3.  마지막 everyone 배열에서는, 최악의 경우 nemo는 가장 마지막에 있습니다. 따라서 위 코드의 for문은 10번을 다 돌아야지 nemo를 찾고 종료됩니다. 이때 시간복잡도는 O(n) 입니다.

2번째의 everyone의 경우에는 nemo가 첫번째에 있기때문에, 입력값이 얼마든간에 시간복잡도는 O(1)이 될 것입니다.

그러나 Big-O는 항상 3번째 everyone과 같이 최악의 경우만을 생각하기 때문에, 이 코드의 시간복잡도는 O(n)이 됩니다.

 

Big-O는 어떤 프로그램이 실행될 때 최대한 걸릴 수 있는 시간만을 고려하기 때문에, 항상 최악의 경우만을 생각합니다.  

 

Rule 2 : Remove Constants ( 상수를 제거한다 )

---

function printFirstItemThenFirstHalfThenSayHi100Times(items) {
    console.log(items[0]); // O(1)

    var middleIndex = Math.floor(items.length / 2);
    var index = 0;

    while (index < middleIndex) { // O(n/2)
        console.log(items[index]);
        index++;
    }

    for (var i = 0; i < 100; i++) { // O(100)
        console.log('hi');
    }
}

위 코드에서, 시간 복잡도는 O(1 + n/2 + 100)입니다(변수 선언이나 작은 계산은 무시하였습니다).

이와 같은 Big-O 표기법을 본 적이 있으신가요...?  

 

사실 위 코드의 시간 복잡도는 O(n) 입니다.  

그 이유는 불필요한 모든 상수를 제거하였기 때문입니다.

큰 틀에서, 우리는 Big-O를 고려할 때 큰 입력값에 대해서만 생각합니다.

n이 10만.. 100만 .. 100억.. 커지면 커질수록, 1, 100과 같은 상수를 더하는 것 혹은 n을 2로 나누는 것 등의 유의미한 효과가 감소됩니다.

따라서 O(1 + n/2 + 100) 에서 n을 제외한 모든 상수는 제거되게되어 O(n)이 위 코드의 시간복잡도가 됩니다.

 

시간복잡도를 표기할때는 불필요한 상수는 제거합니다.

 

Rule 3 : Differents terms for inputs ( 다른 입력에 대해 다른 용어를 사용한다 )

---

function compressBoxesTwice(boxes, boxes2){
  boxes.forEach(function(boxes){
    console.log(boxes);
  });

  boxes2.forEach(function(boxes){
    console.log(boxes);
  });
  
}

// 1. O(n + n) = O(2n) = O(n);
// 2. O(a + b)

위 코드는 서로 다른 입력에대한 두 for문이 차례대로 있는 코드입니다.

위 코드에서 시간 복잡도는 O(n) 이라고 답하기 쉽습니다. boxes에 대한 for문이 n번, boxes2에 대한 for문이 n번이라서 O(n+n) = O(2n)이고, Rule 2에 의하여 불필요한 상수는 제거되어 시간 복잡도는 O(n)이 된다고 생각하기 쉽습니다.

하지만, boxes와 boxes2는 서로 독립적인 입력임을 상기해야 할 필요가 있습니다. boxes가 1개의 입력일 때, boxes2는 1000개의 입력일 수 있습니다.

다시 말해서, 두 배열은 서로 다른 입력이기 때문에 각각 다른 용어를 사용해야 하고, 이때 시간 복잡도는 O(a + b)와 같은 꼴이 됩니다.

a는 boxes에 대한 시간 복잡도, b는 boxes2에 대한 시간 복잡도입니다.

 

다른 입력에 대해서는 각각의 시간을 고려 해주어야 하기때문에, 다른 용어를 사용해야 합니다.

 

Rule 4 : Drop Non Dominants ( 영향력이 없는 항을 제거한다 )

---

function printAllNumbersThenAllPairSums(numbers) {

  console.log('these are the numbers:');
  numbers.forEach(function(number) { // O(n)
    console.log(number);
  });

  console.log('and these are their sums:');
  numbers.forEach(function(firstNumber) { // O(n^2)
    numbers.forEach(function(secondNumber) {
      console.log(firstNumber + secondNumber);
    });
  });
}

printAllNumbersThenAllPairSums([1,2,3,4,5])

위 코드에서 첫번째 for문에서는 시간 복잡도가 O(n)이고, 두번째 for문은 두 for문이 중첩되어 있기 때문에 시간 복잡도가 O(n^2)이 됩니다. 따라서 위 코드의 시간 복잡도는 O(n + n^2)가 됩니다.

그러나, n이 커지면 커질 수록 n^2에 비해 n은 영향력이 사라지게 됩니다.

마치 Rule 2에서 영향력이 없는 상수를 제거하는 것과 같은 방식입니다.

따라서 우리는 n을 제거할 수 있고, 이 코드의 시간 복잡도는 O(n^2)가 되게 됩니다.

만약 O(n^3 + 100n^2 + 300n)과 같은 시간복잡도가 있다고 하면, 3차항인 n^3을 제외한 나머지 항은 모두 삭제할 수 있고 이때 시간복잡도는 O(n^3)이 됩니다. 

 

시간 복잡도에서 영향력이 없는 항은 모두 제거합니다.

수학적으로 설명하면 어떠한 다항식에서 최고차의 항을 제외하고는 모두 제거하는 것으로 설명할 수 있습니다.

 

코드 출처 : Andrei Neagoie to ZTM