시간복잡도/공간복잡도/빅오-표기법

 알고리즘 문제를 푸는데 필수 개념인 시간 복잡도와 공간 복잡도 그리고 이를 표현 하기 위한 대표적인 방법인 빅 오 표긱법에 대해 다룹니다.

▶시간 복잡도 (Time Complexity)

 시간 복잡도는 알고리즘이 작업을 완료하는데 까지 걸리는 시간을 나타내는 지표입니다. 시간 복잡도를 통해 알고리즘이 얼마나 빠르게 동작하는지를 알 수 있습니다.시간 복잡도는 입력 크기에 따른 연산 횟수로 표현되며, 보통 빅 오 표기법(Big O notation)을 사용합니다. 예를 들어, O(n)은 입력 크기에 비례하여 시간이 걸린다는 것을 의미합니다.

▶공간 복잡도 (Space Complexity)

 공간 복잡도는 알고리즘이 실행되는 동안 사용하는 메모리의 양을 나타내는 지표입니다. 이를 통해 알고리즘이 얼마나 많은 메모리를 사용하는지를 파악할 수 있습니다. 공간 복잡도도 입력 크기에 따른 메모리 사용량을 빅 오 표기법(Big O notation)으로 나타냅니다.

▶시간 복잡도와 공간 복잡도의 관계

 시간 복잡도와 공간 복잡도는 효율적인 알고리즘을 선택하거나 개발할 때 중요한 역할을 합니다. 일반적으로 알고리즘이 빠르고 메모리 사용량이 적으면 좋지만, 경우에 따라서는 시간과 공간 중 어느 하나를 희생해야 할 수도 있습니다. 예를 들어, 빠른 실행 시간이 중요한 경우에는 메모리 사용량이 높더라도 시간 복잡도가 낮은 알고리즘을 선택할 수 있습니다. 반대로 메모리 사용량이 중요한 경우에는 시간 복잡도가 높더라도 공간 복잡도가 낮은 알고리즘을 선택할 수 있습니다.

※공간 복잡도가 시간 복잡도보다 엄청 큰 경우는 거의 없다. 시간 복잡도가 작아질 수록 공간 복잡도도 작아지는 경향성이 있기 때문입니다. 시간 복잡도를 O(1) 공간 복잡도를 O(n^2)이상인 코드를 작성하려고 하면 반대와는 다르게 매우 어렵다는 것을 알 수 있습니다.

 

▶빅 오 표기법 (Big O Notation)

 빅 오 표기법은 알고리즘의 복잡도를 표현하는 방법으로, 알고리즘이 입력 크기에 대해 어떻게 동작하는지를 간략하게 나타냅니다. 빅 오 표기법은 알고리즘의 최악의 경우를 기준으로 분석합니다. 표기법은 O( ) 안에 함수를 넣어 표현하며, 이 함수는 입력 크기에 따른 연산 횟수를 나타냅니다. 몇 가지 대표적인 빅 오 표기법 예시는 다음과 같습니다.

 

   ▷ O(1): 상수 시간 (입력 크기와 무관한 고정 시간)

   ▷ O(log n): 로그 시간 (이진 탐색 등)

   ▷ O(n): 선형 시간 (for 문을 통해 입력 데이터를 한 번 순회)

   ▷ O(n log n): 로그 선형 시간 (효율적인 정렬 알고리즘, 예: 병합 정렬, 퀵 정렬)

   ▷ O(n^2): 제곱 시간 (이중 for 문, 이중 루프, 예: 버블 정렬, 삽입 정렬)

   ▷ O(2^n): 지수 시간 (조합, 순열 등)

이미지로 체감 시간을 쉽게 알아보자

▶예제를 통한 이해

주어진 배열의 합을 구하는 알고리즘 코드를 만들어 보겠습니다.

function arraySum(arr) {
  let sum = 0;
  for (let i = 0; i < arr.length; i++) {
    sum += arr[i];
  }
  return sum;
}

이 경우에는 입력 크기는 배열의 길이 인 'n' 입니다.

시간 복잡도는 배열을 for문으로 입력 크기를 한번 순환하므로 O(n) 입니다.

공간 복잡도는 변수가 sum가 i 두개 선언 되어 있기에 입력 크기와 무관한 상수로서 O(1) 입니다.

 

예제를 통해 확인하면서 어느 점도 감이 오셨을 겁니다.

이제 추가 예제 4개를 통해 반복학습을 진행해 보겠습니다.

 

   ▷ 1 번 배열의 최댓값을 구하는 코드

function findMax(arr) {
  let max = arr[0];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > max) {
      max = arr[i];
    }
  }
  return max;
}

       입력은 배열의 크기인 'n' / 시간 복잡도는 for문 한번이므로 O(n) / 공간 복잡도는 max i가 입력과 상수이므로 O(1) 입니다.

       따라서 정답은 입력:'n' / 시간 복잡도 O(n) / 공간 복잡도 O(1)

   ▷ 2 번 주어진 숫자가 소수인지 판별하는 코드

function isPrime(n) {
  if (n <= 1) {
    return false;
  }
  for (let i = 2; i * i <= n; i++) {
    if (n % i === 0) {
      return false;
    }
  }
  return true;
}

       입력의 크기는 'n'이고 시간 복잡도는 범위가 n 이 아닌 sqrt(n)(=>루트를 의미합니다.)이기 때문에 O(sqrt(n)) 공간 복잡도는

       O(1)입니다.

       따라서 정답은 입력:'n' / 시간 복잡도 O(sqrt(n)) / 공간 복잡도 O(1)

   ▷ 3 번 주어진 문자열에서 가장 많이 등장하는 문자를 찾는 코드

function mostFrequentChar(str) {
  let charCount = {};
  for (let i = 0; i < str.length; i++) {
    const char = str[i];
    charCount[char] = (charCount[char] || 0) + 1;
  }

  let maxCount = 0;
  let mostFrequent = '';
  for (const char in charCount) {
    if (charCount[char] > maxCount) {
      maxCount = charCount[char];
      mostFrequent = char;
    }
  }
  return mostFrequent;
}

 입력의 크기는 문자열의 길이인 'n'이고 시간복잡도는 첫 번째 for문에서 n만큼 순회 하므로 O(n) 두 번째 for문은 str의 알파벳 종류 만큼만 순회 하기 때문에 O(n) 보다는 작은 시간 복잡도를 가집니다. 이런 경우 가장 큰 시간복잡도로 근사하기 때문에 이때의 시간 복잡도는 O(n)입니다. 공간 복잡도는 변수가 입력이 증가 할 수록 비례해서 증가하므로 자세하게 설명하면 charCount 객체는 중복되는 알파벳도 임시로 저장해 놓으므로 n에 비례해서 메모리를 차지 합니다. 따라서  O(n)입니다.

       따라서 정답은 입력:'n' / 시간 복잡도 O(n) / 공간 복잡도 O(n)

   ▷ 4 번 주어진 숫자를 거꾸로 뒤집은 숫자를 반환하는 코드

function reverseNumber(n) {
  let reversed = 0;
  while (n > 0) {
    reversed = reversed * 10 + (n % 10);
    n = Math.floor(n / 10);
  }
  return reversed;
}

 동일하게 입력의 크기는 'n'입니다. 입력 크기 만큼 while 반복문이 실행되므로 시간 복잡도는 O(n) 공간 복잡도는 입력과 관계없는 고정갯수 이므로 O(1)입니다.

       따라서 정답은 입력:'n' / 시간 복잡도 O(n) / 공간 복잡도 O(1)