공간 복잡도 판단하기

공간 복잡도란?

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

(입력값과 결과값이 나오는 데까지 사용하는 공간을 말한다.)

입력값이 2배로 늘어났을 때 문제를 해결하는 데 걸리는 공간은 몇 배로 늘어나는 지 보는 것이다.

우리는 공간이 적게 걸리는 알고리즘을 좋아하니 입력값이 늘어나도 걸리는 공간이 덜 늘어나는 알고리즘이 좋은 알고리즘이다.

 

공간 복잡도를 계산 할 때는 저장하는 데이터의 양이 1개의 공간을 의미합니다.

 

첫번째 방법에서 공간 복잡도를 계산 해보자면

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

    for alphabet in alphabet_array: # 총 26개의 공간을 사용합니다.
        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

위에서 사용된 공간들을 더해보면

1) alphabet_array의 길이 = 26

2) max_occurrence, max_alphabet, occurrence 변수 = 3

만큼의 공간이 필요합니다.

그렇다면 이 함수는 29만큼의 공간이 사용 되었구나를 알 수 있다.

 

두번째 방법의 공간 복잡도를 계산 해보면

def find_max_occurred_alphabet(string):

    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(len(alphabet_occurrence_list)): # 26개의 공간을 사용합니다.
        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'))

위에서 사용된 공간들을 더해보면

1) alphabet_array의 길이 = 26

2) arr_index, max_occurrence, max_alphabet_index, alphabet_occurrence 변수 = 4

만큼의 공간이 필요합니다.

그러면 이 함수는 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번 실행

1) alphabet_array 의 길이 X 대입 연산 1번

2) alphabet_array 의 길이 X string의 길이 X (비교 연산 1번 + 대입 연산 1번)

3) alphabet_array 의 길이 X (비교 연산 1번 + 대입 연산 2번)

만큼의 시간이 필요합니다. 여기서 string의 길이는 보통 N이라고 표현하기 때문에

52N + 104만큼의 시간이 걸렸구나!를 알 수 있습니다.

이때 다른 상수 시간의 연산은 시간 복잡도에 큰 영향을 주지 않기 때문에 제외하고 생각하면 됩니다.(지수만 생각)

그러므로 N만큼의 시간이 필요하다고 생각하면 됩니다.

 

두번째 방법의 시간 복잡도는

    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번 실행

1) string의 길이 X (비교 연산 1번 + 대입 연산 2번) 

2) 대입 연산 2번 

3) alphabet_array 의 길이 X (비교 연산 1번 + 대입 연산 3번)

만큼의 시간이 필요합니다. 여기서 string의 길이는 보통 N이라고 표현합니다.

그러면 이 함수는 3N + 106만큼의 시간이 걸렸구나!를 알  수 있고 상수는 계산하지 않아도 되기 때문에

N만큼의 시간이 필요하다고 생각하면 됩니다.

 

첫번째 방법과 두번째 방법의 시간 복잡도와 비교를 위해서 N^2도 넣어 봤습니다.

이 표를 보면 두가지를 알 수 있습니다.

1) 52N + 104이든 3N + 106이든 N^2에 비해서 아무것도 아니구나를 알 수 있고

2) 공간 복잡도 보다는 시간 복잡도를 더 신경 써야 한다!는 걸 알 수 있습니다.

 

다시 한 번 정리 하자면 상수는 성능에 큰 차이를 주지 않습니다.

그렇기 때문에 시간 복잡도를 비교 할 때는 지수를 신경 써서 알고리즘을 짜야 더 효율적인 알고리즘을 짤 수 있습니다.

+ 공간 복잡도 보다는 시간 복잡도를 더 신경 써야 한다.