💾 [CS] 알고리즘의 공간 복잡도(Space Complexity)란 무엇일까요?

• 공간 복잡도(Space Complexity)는 알고리즘이 실행되는 동안 사용하는 메모리 공간의 양을 측정하는 지표입니다.
• 시간 복잡도(Time Complexity)가 알고리즘의 실행 시간을 평가하는 것이라면, 공간 복잡도(Time Complexity)는 알고리즘이 얼마나 많은 메모리를 사용하는지를 평가하는 개념입니다.

1️⃣ 왜 공간 복잡도가 중요한가요?

1️⃣ 메모리 효율성.

• 메모리는 제한된 자원입니다.
  • 특히 임베디드 시스템이나 모바일 애플리케이션처럼 메모리 자원이 제한된 환경에서 공간 복잡도(Space Complexity)를 고려하지 않으면 메모리 부족으로 프로그램이 충돌하거나 성능이 저하될 수 있습니다.

📝 임베디드 시스템(Embedded System)

특정 기능을 수행하기 위해 설계된 독립적인 컴퓨터 시스템으로, 일반적인 컴퓨터와 달리 특정 목적이나 작업에 최적화가 되어 있습니다.
임베디드 시스템(Embadded System)은 하드웨어와 소프트웨어가 조합되어 특정 장치나 시스템의 일부로 내장되며, 자동차, 가전제품, 의료기기, 산업 장비, 가전 제품 등 다양한 곳에서 사용됩니다.

2️⃣ 성능 최적화.

• 때로는 알고리즘의 실행 속도뿐만 아니라 메모리 사용량도 최적화해야 합니다.
  • 공간 복잡도(Space Complexity)를 줄이면 프로그램의 전반적인 성능이 향상될 수 있습니다.

3️⃣ 알고리즘 비교.

• 두 알고리즘이 같은 시간 복잡도(Time Complexity)를 가지더라도, 공간 복잡도(Space Complexity)가 낮은 알고리즘(Algorithm)이 더 효율적일 수 있습니다.

2️⃣ 공간 복잡도의 정의.

• 공간 복잡도(Time Complexity)는 알고리즘이 실행되면서 사용하는 총 메모리 양을 의미합니다.
  • 이 메모리는 다음 두 가지로 나뉩니다.
    • 1. 고정 공간(Fixed Part)
    • 1. 가변 공간(Variable Part)

1️⃣ 고정 공간(Fixed Part)

• 알고리즘이 고정된 크기로 사용하는 메모리입니다.
  • 입력 크기와 무관하게 항상 일정한 공간을 차지합니다.
• 예를 들어, 알고리즘에서 사용하는 상수, 변수, 함수 호출, 그리고 특정 크기의 고정 배열 등이 포함됩니다.
• 일반적으로 O(1)로 표현됩니다.

2️⃣ 가변 공간(Variable Part)

• 입력 크기에 따라 변화하는 메모리입니다.
• 예를 들어, 동적 배열, 재귀 호출 시 사용되는 스택 공간, 데이터를 저장하기 위한 임시 배열 등이 여기에 해당합니다.
• 가변 공간(Variable Part) 크기는 입력 크기에 따라 달라지며, 공간 복잡도(Space Complexity)의 중요한 요소가 됩니다.

3️⃣ 빅-오 표기법(Big-O Notation)으로 공간 복잡도 표현.

• 공간 복잡도(Space Complexity)도 시간 복잡도(Time Complexity)처럼 빅-오 표기법(Big-O Notation)을 사용하여 표현합니다.
  • 이는 입력 크기(n)가 커질 때 메모리 사용량이 얼마나 빠르게 증가하는지를 나타냅니다.

1️⃣ 주요 공간 복잡도 예시.

1️⃣ O(1) 👉 상수 공간(Constant Space)

• 알고리즘이 입력 크기와 관계없이 일정한 양의 메모리를 사용하는 경우.
• 예: 변수 3개만을 사용하는 알고리즘.

  int add(int a, int b) {
    int sum = a + b;
    return sum;
  }
  

• 위 함수는 a, b, sum이라는 3개의 변수만을 사용하므로 O(1)의 공간 복잡도(Space Complexity)를 가집니다.

2️⃣ O(n) 👉 선형 공간(Linear Space)

• 입력 크기 n에 비례하여 메모리 공간이 증가하는 경우.
• 예: 크기가 n인 배열을 사용하는 알고리즘.

  int[] copyArray(int[] arr) {
    int[] newArr = new int[arr.length];
    for (int i = 0; i < arr.length; i++) {
        newArr[i] = arr[i];
    }
    return newArr;
  }
  

• 입력 배열의 크기 n에 비례하는 크기의 새로운 배열 newArr를 생성하므로 O(n)의 공간 복잡도(Space Complexity)를 가집니다.

3️⃣ O(n^2) 👉 이차 공간(Quadratic Space)

• 메모리 사용량이 입력 크기의 제곱에 비례하여 증가하는 경우.
• 예: 크기 n * n인 2차원 배열을 사용하는 알고리즘.

int[][] generateMatrix(int n) {
    int [][] matrix = new int[n][n];
    // 메모리 사용량이 n^2에 비례
    return martix;
}

4️⃣ 예시를 통한 공간 복잡도 분석.

1️⃣ O(1) 공간 복잡도.

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

• 분석
  • 이 함수는 입력 배열의 크기와 상관없이 max와 i 두 개의 변수만 사용합니다.
    • 따라서 공간 복잡도(Space Complexity)는 O(1)입니다.

2️⃣ 재귀 알고리즘의 공간 복잡도.

int factorial(int n) {
    if(n <= 1) {
        return 1;
    }
    return n * fatorial(n - 1);
}

• 분석
  • 이 재귀 함수는 스택(Stack)을 사용하여 각 함수 호출을 저장합니다.
    • factorial(5)를 호출하면 내부적으로 factorial(4), factorial(3) 등이 호출되며, 호출이 끝나기 전까지 각 호출이 스택(Stack)에 저장됩니다.
  • 재귀 깊이는 최대 n이 되므로, 공간 복잡도는 O(n)입니다.

5️⃣ 공간 복잡도 최적화 방법.

1️⃣ 데이터 구조 선택.

• 더 적은 메모리를 사용하는 효율적인 데이터 구조를 사용합니다.
  • 예를 들어, 고정 크기의 배열 대신 동적 배역(ArrayList)을 사용하여 메모리를 절약할 수 있습니다.

2️⃣ 인플레이스(In-Place) 알고리즘.

• 입력 데이터를 그 자리에서 직접 수정하는 방식으로 메모리 사용을 최소화합니다.
  • 예를 들어, 배열을 정렬할 때 새로운 배열을 생성하지 않고 기존 배열을 정렬하는 방식으로 공간 복잡도(Space Complexity)를 O(1)로 줄일 수 있습니다.

3️⃣ 재귀 대신 반복문 사용.

• 재귀 호출로 인한 스택 메모리(Stack Memory) 사용을 줄이기 위해 반복문을 사용할 수 있습니다.
  • 재귀 함수가 깊은 재귀 호출을 통해 많은 메모리를 사용하는 경우, 이를 반복문으로 대체하면 공간 복잡도(Space Complexity)를 줄일 수 있습니다.

6️⃣ 요약.

• 공간 복잡도(Space Complexity)는 알고리즘(Algorithm)이 실행 중 사용하는 메모리의 양을 나타내며, 효율적인 알고리즘(Algorithm) 설계에 중요한 요소입니다.
• 이는 입력 크기에 따라 증가하는 메모리 사용량을 분석하며, 빅-오 표기법(Big-O Notation)을 사용하여 표현됩니다.
• 공간 복잡도(Space Complexity)를 잘 이해하면, 메모리 효율성을 높이고, 프로그램 성능을 최적화할 수 있습니다.