[알고리즘] 공간복잡도 파악하기

2021.06.12 - [알고리즘] - [알고리즘] 시간 복잡도 판단하기

[알고리즘] 시간 복잡도 판단하기

공간복잡도란?

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

입력값이 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
    max_alphabet = alphabet_array[0]

    for alphabet in alphabet_array:
        occurrence = 0
        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
print("정답 = a 현재 풀이 값 =", result("Hello my name is sparta"))
print("정답 = a 현재 풀이 값 =", result("Sparta coding club"))
print("정답 = s 현재 풀이 값 =", result("best of best sparta"))

 

 

총 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')
        alphabet_occurrence_list[arr_index] += 1

    max_occurrence = 0
    max_alphabet_index = 0
    for index in range(len(alphabet_occurrence_list)):
        alphabet_occurrence = alphabet_occurrence_list[index]
        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
print("정답 = a 현재 풀이 값 =", result("Hello my name is sparta"))
print("정답 = a 현재 풀이 값 =", result("Sparta coding club"))
print("정답 = s 현재 풀이 값 =", result("best of best sparta"))

30만큼의 공간을 사용한다

---

둘다 상수라서 여기에서는 적게 썼다고 더 효율적인 방법이라고 말할 수 없다.

그래서 비교를 시간 복잡도로 비교하면 된다.

대부분의 알고리즘 성능은 공간에 의해서 결정되지 않는다.

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