[알고리즘] 공간 복잡도 (Space Complexity)

공간 복잡도란?

알고리즘이 문제를 완전히 해결하는데 필요한 메모리 크기입니다. 입력값이 2배로 커졌을 때 문제를 해결하는 데 메모리가 몇 배나 커지는지 확인해야 하며 메모리를 적게 사용하는 알고리즘이 좋은 알고리즘입니다.

 

최빈값 찾기 알고리즘의 공간 복잡도 판단해보기

1. alphabet_array의 길이 = 26
    max_occurrence, max_alphabet, occurrence 변수 = 3
    29만큼의 공간을 사용

# a~z까지, 26개의 공간을 사용
alphabet_array = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "x", "y", "z"]

max_occurrence = 0                 # 1개의 공간을 사용합니다
max_alphabet = alphabet_array[0]   # 1개의 공간을 사용합니다.

for alphabet in alphabet_array:
	occurrence = 0                 # 1개의 공간을 사용합니다

 

2. alphabet_array 의 길이 = 26
    arr_index, max_occurrence, max_alphabet_index, alphabet_occurrence 변수 = 4
    30만큼의 공간을 사용

# 26개의 공간을 사용
alphabet_occurrence_list = [0] * 26 

for char in string:
    if not char.isalpha():
        continue
    arr_index = ord(char) - ord('a')  # 1개의 공간을 사용합니다
    alphabet_occurrence_list[arr_index] += 1

    max_occurrence = 0                   # 1개의 공간을 사용합니다
    max_alphabet_index = 0               # 1개의 공간을 사용합니다
    for index in range(26):
        alphabet_occurrence = alphabet_occurrence_list[index] # 1개의 공간을 사용합니다
        if alphabet_occurrence > max_occurrence:
            max_occurrence = alphabet_occurrence
            max_alphabet_index = index

 

결과 비교

공간을 더 적게 쓴 첫 번째 방법이 더 효율적인 것일까요? 29와 30은 차이가 크지 않아 큰 상관이 없습니다. 대부분의 문제에서 알고리즘의 성능이 공간에 의해서 결정되지 않습니다. 따라서 공간 복잡도보다는 시간 복잡도를 더 신경 써야 합니다.