시간복잡도 (Time Complexity)

시간 복잡도를 고려한 풀이? 🤔

• 코딩 테스트 문제를 처음 풀었을 때 문제를 풀기에 급급했지만 막상 테스트에 통과하고 난 후 이 코드가 맞나? 이게 효율적인가?라는 생각을 해본 적이 있다면 이미 시간 복잡도에 대해 고민해 본 것이나 다름없다!
• 시간 복잡도를 고려한다는 건 입력값에 따라 로직이 실행되는 시간이 증가하고 감소하는 시간의 비율을 최소화하여 구성했다는 뜻이다.
• 시간 복잡도는 3가지의 표기법이 있는데
  • Big-O(빅-오) -> 최악을 고려 ( 걸리는 시간의 최대를 고려 )
  • Big-Ω(빅-오메가) -> 최선을 고려 ( 걸리는 시간의 최선을 고려 )
  • Big-θ(빅-세타) -> 평균을 고려 ( 걸리는 시간의 평균을 고려 )

 

• 시간 복잡도에서 가장 자주 사용되는 표기법은 빅오 표기법으로 최악을 고려해야 한다. 즉 효율을 고려할 때 입력값의 따라 최대 ~~ 까지 시간이 걸릴 수 있다를 고려해야 한다.
• 빅오 표기법을 사용하는 이유는 빅-오메가 처럼 최선을 고려할 경우 10초가 나왔어야 하는 게 50초가 나오게 되면 해당 문제에 대해 문제가 발생한 구간을 찾아 해결하기 위한 시간이 많이 들어가게 된다. 위 이유로 빅-세타 또한 같은 문제가 발생한다.

 

Big-O 표기법의 종류

출처 :  http://bigocheatsheet.com/

- O(1) (constant complexity) 일정한 복잡도

• 가장 빠른 시간복잡도로 입력값의 크기에 상관없이 즉시 출력 값을 얻어낸다.

const arr = [1, 2, 3];

const testFn = (arr) => {
  return arr[1];
};

test(arr); // 2

• 어떤 배열이 들어가든 1번째 index값을 뱉어내는 이 함수의 시간 복잡도는 (O)1 이다.
• arr배열의 요소가 10000개 있어도 즉시 값을 반환한다.

 

- O(log n) (logarithmic complexity) 로그 복잡도

• O(1) 다음으로 빠른 시간 복잡도를 가진다.
• 대표적으로 이진 탐색(Binary Search Algorithm)이 해당 시간 복잡도를 가진다.

 

• 이해하기 쉬운 게임으로 비유해 보자면 up & down을 예로 들 수 있다.
  1. 1~50 중 하나의 숫자를 고른다. (20)
  2. 25(가운데) 숫자를 제시하면 20보다 큼으로 down을 외친다.
  3. 1~25중의 하나의 숫자이므로 또다시 경우의 수를 절반으로 줄이기 위해 12를 제시한다.
  4. 12보다 크므로 up을 외친다.
  5. 경우의 수를 계속 절반으로 줄여나가며 정답을 찾는다

 

- O(n) (linear complexity) 선형 복잡도

• 입력값이 1일 때 1초, 100일 때 100초가 걸린다면 그건 O(n)의 시간 복잡도를 가진다고 할 수 있다.

const testFn = (n) => {
  for (let i = 0; i < n; i++) {
    console.log(i);
  }
};

const testFn2 = (n) => {
  for (let i = 0; i < 2n; i++) {
    console.log(i);
  }
  for (let j = 0; j < n; j++) {
    console.log(j);
  }
};

// testFn[O(n)] 과 testFn2[O(2n)] 의 시간복잡도는 같다.

• 간단하게 for문, filter, map 등이 O(n)의 시간복잡도를 가진다. 입력값이 증가함에 따라 시간이 같은 비율로 증가한다.
  • testFn2 함수는 2개의 for문으로 O(2n)이라고 생각할 수도 있지만, Big-O 표기법에서는 모두 다 O(n)이라고 표현한다. 

- O(n log n) (linearithmic time) 로그 선형 알고리즘

• 선형(linear) 알고리즘 보다 약간 느리고 대표적으로 병합 정렬 알고리즘이 있다.

 

- O(n^2) (quandratic complexity) 2차 복잡도

• 입력값이 1일 때 1초가 걸리던 코드에 5를 줬을 때 25초가 걸리게 된다면 이 코드는 O(n^2)의 시간 복잡도를 가진다고 할 수 있다.

const testFn = (n) => {
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      //내용
    }
  }
};

const testFn2 = (n) => {
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      for (let k = 0; k < n; k++) {
        //내용
      }
    }
  }
};

// testFn[O(n^2)] 과 testFn2[O(n^3)] 의 시간복잡도는 같다.

• 2중, 3중 for문이 O(n^2)에 해당한다. O(n)의 시간 복잡도와 마찬가지로 O(n^2)이든 O(n^3) 이든 O(n^2)로 표기한다.

 

- O(2^n) (exponentialcomplexity) 기하급수적 복잡도

• Big-O 표기법 중 가장 느린 시간 복잡도다. 내가 구현한 알고리즘이 이 시간 복잡도를 가진다면 다시 한번 고민해보자.
  
  • 해당 시간 복잡도는 재귀 함수, 피보나치수열과 관련이 있는데 아직 공부를 못했기에 나중에 추가할 예정이다.