First Step

Time-Complexity And Big O

Time-Complexity

시간 복잡도는 해당 코드가 얼마나 많은 연산을 필요로 하는지를 나타내는 척도이다. Big O, Ω, Θ 등 다양하게 있지만 보통 프로그래밍에서 시간복잡도를 말할 때 Big O를 사용한다(각 차이는 뒤에서 설명).

Big O

Big O는 특정 범위의 시간을 기준으로 알고리즘의 시간복잡도를 분석하는 방법이다. 특정 범위의 시간이라고 말한 이유는 예로, 어떤 것을 한번 실행할 때 0.3초 걸리던 것이 1000번 실행할 때 0.33초로 느려진 경우를 보는 것이 아니라 30초로 느려지는 경우를 알고 싶어하는 것이다.

미세한 차이들을 접어두고 시간에 가장 중요한 변수가 되는 부분을 나타내는 방법으로 봐도 될 것이다.

2차 방정식을 예로 들어보자, 3x^2 + x + 1 x를 5로 정하면, 75 + 5 + 1 이다. 여기서 숫자를 대입했을 때 가장 큰 비중을 차지하는 숫자가 몇번째 숫자인가? 3x^2 인 75일 것이다. 그러나 이것도 보면, 3 * x^2 이다. 이 중에 가장 중요한 변수를 고르면, x^2 이다. (여기서 당연한 팁, 대입하는 x값이 클수록 그 차이는 더 분명할 것이다.) 그러므로 3x^2 + x + 1 의 Big O는 O(n^2) 가 되는 것이다.

O(1)

constant. 상수 즉, 우리가 정해놓은 만큼만 복잡한 정도를 뜻한다. 예를 들어, 
for (var i = 0; i <= 5; i += 1) {
  console.log(i);
}
위의 코드는 반복문을 총 6번 실행하는 것을 알 수 있는데, 이는 
O(1)
에 해당된다.

O(n)

linear. 변수의 크기만큼 복잡한 정도를 뜻한다. 예를 들면 아래의 코드는 
O(n)
만큼 복잡한 코드이다. 
for (var i = 0; i <= n; i += 1) {
  console.log(i);
}
주의할 점은, 
2n
이나 
3n
, 
100n
등은 모두 
O(n)
만큼 복잡하다고 본다. n 앞에 붙은 계수는 상수이므로, 변수인 n의 크기가 크면 클수록 무시할 수 있을 만큼 작다고 가정하기 때문이다. 따라서 아래의 코드도 
O(n)
에 해당된다. 
for (var i = 0; i <= n; i += 1) {
  console.log(i);
}
for (var i = 0; i <= n; i += 1) {
  console.log(i);
}
for (var i = 0; i <= n; i += 1) {
  console.log(i);
}

O(n^2)

quadratic. 변수의 제곱만큼 복잡한 정도를 뜻한다. 보통 반복문 내에 반복문이 또 있는 경우가 해당된다. 
for (var i = 0; i <= n; i += 1) {
  for (var j = 0; j <= n; j += 1) {
    console.log(i, j);
  }
}
위와 같은 코드가 
O(n^2)
에 해당된다. 만약 시간 복잡도가 
2n^2 + 5n + 3
이라고 해도, 
O(n^2)
으로 간주한다. 
n^2
의 계수나, 그보다 낮은 차수의 항들은 
n^2
에 비해 작은 수이기 때문이다.

O(log n)

logarithmic. 말 그대로 로그 시간이 걸린다는 뜻이다. 보통 log의 밑은 2로 사용하며 대표적으로 이진 검색 알고리즘(binary search algorithm)이 있다. 예를 들어, 변수가 1048576일 때 
O(log n)
의 시간 복잡도를 갖는 코드는 20의 복잡도를 갖는다.
왜냐하면, 
log,[object Object],1048576 === 20
이기 때문이다. 굉장히 효율적인 케이스이다.

O(n log n)

linear log. 
O(log n)
이 n번 반복되었을 때의 시간 복잡도이다. 병합 정렬(merge sort)의 시간 복잡도가 이에 해당된다. 이해를 위해서는 알고리즘에서 중요한 개념인 Divide and conquer를 살펴보면 된다.

Big O, Θ, Ω

참고로, 여기서 O를 영어 오를 대문자로 표기했지만 실제로는 세타(Θ)와 혼용되어 이해를 한다.
O 는 원래 '가장 최악의 시나리오' 또는 upper bound를 말하며
Θ 는 최악과 '최상의 시나리오' 또는 tight bound (upper and lower bound)를 말한다.
즉,
O는 ~ 보다 빠르게 늘어나지 않는다.
Θ는 ~ 만큼 빠르게 늘어난다.
라고 말하는 것이며, 각 알고리즘마다 분리해서 이해하는 것이 좋으나,
그러지 않고 O를 말하면서 기존의 해석과는 달리 평균적으로 어느정도다로 사용되는 경우가 대부분이다.

좀 더? 오메가(Ω)의 경우 '최상의 시나리오' 또는 lower bound라고 한다.
O 최악
Ω 최상
Θ 둘다(둘다 라는 말은 Θ가지고 최악과 최상을 혼용해서 써도 된다는 말이다.)
개인적으로는, Big O를 아는 사람 또는 사람들을 만났을 때, 상대방 또는 다수가 말하는 이해의 정도에 맞추어서 하는 것을 추천한다.

실제 자바스트립트 알고리즘을 살펴보자.
function crossAdd(input) {
    var answer = [];
    for (var i = 0; i < input.length; i++) {
        var goingUp = input[i];
        var goingDown = input[input.length-1-i];
        answer.push(goingUp + goingDown);
    }
    return answer;
}
이 function의 Big O는?

또 하나를 살펴보자.
function find(needle, haystack) {
    for (var i = 0; i < haystack.length; i++) {
        if (haystack[i] === needle) return true;
    }
}
이 function의 Big O는?

그렇다면, 
function makeTuples(input) {
  var answer = [];
  for (var i = 0; i < input.length; i++) {
      for (var j = 0; j < input.length; j++) {
          answer.push([input[i], input[j]]);
      }
  }
  return answer;
}
이 function의 Big O는?

(힌트: loop 안에 loop)

loop 안에 loop 안에 loop는?

Big O에 대한 답안지.


Big O CheatSheet