시간 복잡도(Time Complexity) 와 공간 복잡도(Space Complexity)

---

공간 복잡도(Space Complexity)

---

O(1) - 상수 공간(Constant Space)

• 정의:

  • 입력 데이터의 크기와 관계없이 알고리즘이 항상 동일한 양의 메모리를 사용합니다.

• Python 예시:

def add_numbers(a, b):
    return a + b

• C 예시:

#include <stdio.h>

int addNumbers(int a, int b) {
    return a + b;
}

• 사용 사례:
  • 단순 변수 선언 및 값 반환
  • 스택에서 최상단 원소 접근

[[O(n) - 선형 공간]]

---

O(n) - 선형 공간(Linear Space)

• 정의:

  • 입력 데이터의 크기에 비례하여 사용되는 메모리 양이 선형적으로 증가합니다.

• Python 예시:

def create_list(n):
    return [i for i in range(n)]

• C 예시:

#include <stdio.h>
#include <stdlib.h>

int* createArray(int n) {
    int* arr = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        arr[i] = i;
    }
    return arr;
}

• 사용 사례:
  • 배열이나 리스트의 생성 및 초기화

[[O(n^2) - 제곱 공간]]

---

O(n^2) - 제곱 공간(Squared Space)

• 정의:

  • 입력 데이터의 크기의 제곱에 비례하여 메모리가 사용됩니다.

• Python 예시:

def create_matrix(n):
    return [[0 for _ in range(n)] for _ in range(n)]

• C 예시:

#include <stdio.h>
#include <stdlib.h>

int** createMatrix(int n) {
    int** matrix = (int**)malloc(n * sizeof(int*));
    for (int i = 0; i < n; i++) {
        matrix[i] = (int*)malloc(n * sizeof(int));
        for (int j = 0; j < n; j++) {
            matrix[i][j] = 0;
        }
    }
    return matrix;
}

• 사용 사례:
  • 2차원 배열 또는 매트릭스의 생성 및 초기화

[[O(n log n) - n log n 공간]]

---

O(n log n) - ( n \log n ) 공간

• 정의:

  • 이러한 복잡도를 직접적으로 공간 복잡도에서 볼 수는 없습니다.
  • 주로 시간 복잡도에서 볼 수 있는 복잡도입니다.
  • 병합 정렬이나 힙 정렬과 같은 정렬 알고리즘에서 볼 수 있습니다.

• 사용 사례:

  • 병합 정렬이나 힙 정렬과 같은 정렬 알고리즘에서 볼 수 있으나, 공간 복잡도로서는 이러한 패턴이 드뭅니다.

---