24.12.24 TIL 공간복잡도

1. 공간복잡도(Space Complexity)란?

공간복잡도는 알고리즘을 실행할 때 필요한 메모리의 양을 나타냅니다.
시간복잡도가 실행 시간의 효율성을 분석한다면, 공간복잡도는 메모리 사용량의 효율성을 분석합니다.

---

2. 왜 중요한가?

1. 메모리 제한 고려: 임베디드 시스템이나 메모리 제한이 있는 환경에서 중요
2. 성능 최적화: 메모리를 적게 사용하면 더 많은 데이터를 처리할 수 있습니다.
3. 시간과 공간의 균형: 성능 최적화를 위해 시간과 공간의 트레이드오프를 고려해야 합니다.

---

3. 공간복잡도의 구성 요소

공간복잡도는 고정 공간과 가변 공간의 합으로 계산됩니다.

1. 고정 공간 (Fixed Space)

   • 입력 크기와 상관없이 항상 일정한 공간을 사용
   • 예: 상수, 변수, 프로그램 코드 등

2. 가변 공간 (Variable Space)

   • 입력 크기에 따라 달라지는 공간
   • 예: 동적 할당된 배열, 재귀 호출 스택 등

---

4. 공간복잡도의 Big-O 표기법

Big-O 표기법을 통해 입력 크기 ( n )에 따라 메모리 사용량의 증가율을 나타냅니다.

주요 예시

1. ( O(1) ): 상수 공간

   • 추가 공간이 거의 필요 없음
   • 예: 단순 반복문

   int sumArray(int[] arr) {
       int sum = 0; // O(1) 공간 사용
       for (int i = 0; i < arr.length; i++) {
           sum += arr[i];
       }
       return sum;
   }

2. ( O(n) ): 선형 공간

   • 입력 크기만큼의 메모리를 할당
   • 예: 배열이나 리스트 생성

   int[] createArray(int n) {
       return new int[n]; // O(n) 공간 사용
   }

3. ( O(n^2) ): 제곱 공간

   • 2차원 배열이나 행렬 생성 시 발생
   • 예: 그래프 인접 행렬

---

5. 재귀와 공간복잡도

재귀 함수는 호출될 때마다 호출 스택에 데이터를 저장하므로, 공간복잡도가 증가합니다.

예시: 피보나치 수열 (재귀)

int fibonacci(int n) {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

• 재귀 깊이: ( O(n) )
• 호출 스택 공간 사용: ( O(n) )

---

6. 시간복잡도와의 트레이드오프

알고리즘 설계 시 시간복잡도와 공간복잡도를 함께 고려해야 합니다.
종종 공간을 더 많이 사용하여 시간을 줄이거나, 시간을 더 들여 공간을 줄이는 선택을 해야 합니다.

예시: 피보나치 수열

1. 재귀: 공간복잡도 ( O(n) ), 시간복잡도 ( O(2^n) )
2. 동적 프로그래밍: 공간복잡도 ( O(n) ), 시간복잡도 ( O(n) )
3. 변수만 사용: 공간복잡도 ( O(1) ), 시간복잡도 ( O(n) )

---

7. 실제 개발에서의 적용

1. 메모리 제한 확인: 대규모 데이터를 처리하거나 임베디드 시스템 개발 시 메모리 제한을 고려
2. 데이터 구조 선택: 공간효율적인 자료구조(예: 배열, 해시맵) 선택
3. 불필요한 데이터 제거: 사용하지 않는 객체나 변수는 명시적으로 제거
4. 재귀 최적화: 재귀 호출 대신 반복문 사용하거나 메모이제이션 적용

---

8. 마무리

공간복잡도는 시간복잡도만큼 중요한 개념임을 느꼈습니다. 특히 대규모 데이터를 다루거나 메모리 자원이 제한된 환경에서의 개발 경험은, 메모리 관리와 효율성의 중요성을 다시금 깨닫게 해줍니다. 앞으로 더 복잡한 문제를 해결할 때도 효율성과 안정성을 최우선으로 고려해야겠습니다.