공간복잡도

입력값과 문제를 해결하는 데 걸리는 공간과의 상관관계를 말한다.
입력값이 2배로 늘어났을 때 문제를 해결하는 데 걸리는 공간은
몇 배로 늘어나는지를 보는 것이다.
우리는 공간이 적게 걸리는 알고리즘을 좋아하니 입력값이 늘어나도 걸리는 공간이 덜 늘어나는 알고리즘이 좋은 알고리즘이다.

공간복잡도 판단

첫번째 방법

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

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"))

저장하는 데이터의 양이 1개의 공간을 사용한다고 계산

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개의 공간을 사용합니다

• 위에서 사용된 공간들을 더해보면,
  1. alphabet_array 의 길이 = 26
  2. max_occurrence, max_alphabet, occurrence 변수 = 3

두번째 방법

		alphabet_occurrence_list = [0] * 26 # -> 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

• 위에서 사용된 공간들을 더해보면,
  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이라고 표현한다. 그러면 위의 시간을 다음과 같이 표현할 수 있다

26(1 + 2N + 3) = 52N + 104

이제 이 함수는 $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번 실행 

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

만큼의 시간이 필요합니다. 여기서 string 의 길이는 보통 N이라고 표현한다. 그러면 위의 시간을 다음과 같이 표현할 수 있다.


> 

N (1 + 2) + 2 + 26 (1 + 3) = 3N + 106

이제 이 함수는 $3N+106$ 만큼의 시간이 걸렸겠구나! 생각할 수 있다.