공간 복잡도

정창민·2022년 11월 22일

공간 복잡도란?

입력값과 문제를 해결하는 데 걸리는 공간과의 상관관계를 말한다.

첫 번째 방법

def find_max_occurred_alphabet(string):
    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"]	# -> 26 개의 공간을 사용합니다
    max_occurrence = 0	# 1개의 공간을 사용합니다
    max_alphabet = alphabet_array[0]	# 1개의 공간을 사용합니다.

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

        if occurrence > max_occurrence:	
            max_alphabet = alphabet
            max_occurrence = occurrence

    return max_alphabet

result = find_max_occurred_alphabet

위 연산들을 다 더해봤을 때
- alphabet_array 의 길이 = 26
- max_occurrence, max_alphabet, occurrence 변수 = 3
29
만큼의 공간이 필요, 이 함수는 $29$ 만큼의 공간이 사용되었구나! 라고 말할 수 있다.

두 번째 방법

def find_max_occurred_alphabet(string):
    alphabet_occurrence_list = [0] * 26	# -> 26 개의 공간을 사용합니다

    for char in string:
        if not char.isalpha():
            continue
        arr_index = ord(char) - ord('a')
        alphabet_occurrence_list[arr_index] += 1

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

    return chr(max_alphabet_index + ord('a'))


result = find_max_occurred_alphabet

위 연산들을 다 더해봤을 때
- alphabet_array 의 길이 = 26
- arr_index, max_occurrence, max_alphabet_index, alphabet_occurrence 변수 = 4
30
만큼의 공간이 필요, 이 함수는 $30$ 만큼의 공간이 사용되었구나! 라고 말할 수 있다.

?

그러면, 공간을 더 적게 쓴 첫 번째 방법이 더 효율적인걸까?

29와 30 모두 상수라 큰 상관이 없다.

그러면 뭘로 비교하는 게 좋을까?
바로 시간 복잡도로 비교하시면 된다.

이처럼, 대부분의 문제에서는 알고리즘의 성능이 공간에 의해서 결정되지 않는다. 따라서 공간 복잡도보다는 "시간 복잡도"를 더 신경 써야 한다.

첫 번째 방법 - 시간 복잡도

		 for alphabet in alphabet_array:    # alphabet_array 의 길이(26)만큼 아래 연산이 실행
        occurrence = 0                  # 대입 연산 1번 실행
        for char in string:             # string 의 길이만큼 아래 연산이 실행
            if char == alphabet:        # 비교 연산 1번 실행
                occurrence += 1         # 대입 연산 1번 실행 

        if occurrence > max_occurrence: # 비교 연산 1번 실행
            max_alphabet = alphabet     # 대입 연산 1번 실행
            max_occurrence = number     # 대입 연산 1번 실행

위에서 연산된 것들을 더해보면,
- alphabet_array 의 길이 X 대입 연산 1번
- alphabet_array 의 길이 X string의 길이 X (비교 연산 1번 + 대입 연산 1번)
- alphabet_array 의 길이 X (비교 연산 1번 + 대입 연산 2번)
26 (1 + 2 N + 3) = 52N + 104

두 번째 방법

    for char in string:        # string 의 길이만큼 아래 연산이 실행
        if not char.isalpha(): # 비교 연산 1번 실행
            continue
        arr_index = ord(char) - ord('a')         # 대입 연산 1번 실행 
        alphabet_occurrence_list[arr_index] += 1 # 대입 연산 1번 실행 

    max_occurrence = 0        # 대입 연산 1번 실행 
    max_alphabet_index = 0    # 대입 연산 1번 실행 
    for index in range(len(alphabet_occurrence_list)):    # alphabet_array 의 길이(26)만큼 아래 연산이 실행
        alphabet_occurrence = alphabet_occurrence_list[index] # 대입 연산 1번 실행 
        if alphabet_occurrence > max_occurrence: # 비교 연산 1번 실행 
            max_occurrence = alphabet_occurrence # 대입 연산 1번 실행 
            max_alphabet_index = index           # 대입 연산 1번 실행

위에서 연산된 것들을 더해보면,
- string의 길이 X (비교 연산 1번 + 대입 연산 2번)
- 대입 연산 2번
- alphabet_array 의 길이 X (비교 연산 1번 + 대입 연산 3번)
N (1 + 2) + 2 + 26 (1 + 3) = 3N + 106