공간 복잡도 판단하기

[공간 복잡도란?]

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

(공간은 변수나 배열 등 값을 담을 때 쓰이는 것들을 말함)

"우리는 공간이 적게 걸리는 알고리즘을 좋아하니

 입력값이 늘어나도 걸리는 공간이 덜 늘어나는 알고리즘이 좋은 알고리즘이겠죠?"

 

---

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

방법1) 

각 알파벳마다 문자열들을 돌면서 몇 글자가 나왔는 지 확인

만약 그 숫자가 저장한 알파벳 빈도 수보다 크면, 그 값을 저장하고 제일 큰 알파벳으로 저장.

def find_max_occurred_alphabet(string):
    # alphabet_array: 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개의 공간을 사용합니다
        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개의 공간을 사용한다고 계산하면 됨!!

1. alphabet_array의 공간 26개

2. max_occurence, max_alphabet, occurence 변수 총 3개

총 29

29만큼의 공간이 필요!

결론) 위의 함수는 29만큼의 공간이 사용되었구나 라고 할 수 있음

 

 

방법2)

각 알파벳의 빈도수를 배열에 저장한 다음, 빈도수 중 가장 많은 알파벳의 인덱스 값을 반환

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')            # 1개의 공간을 사용합니다
        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
print("정답 = a 현재 풀이 값 =", result("Hello my name is sparta"))
print("정답 = a 현재 풀이 값 =", result("Sparta coding club"))
print("정답 = s 현재 풀이 값 =", result("best of best sparta"))

1. alphabet_array의 길이 26

2. arr_index, max_occurence, max_alphabet_index, alphabet_occurence 변수 총 4

총 30

결론) 이 함수는 30만큼의 공간이 사용되었구나 라고 할 수 있음

 

 

공간을 더 적게 쓴 첫 번째 방법이 더 효율적인가요?!!??!!!

29와 30 모두 상수이기 때문에 큰 상관이 없음!

대부분의 문제에서는 알고리즘의 성능이 공간에 의해서 결정되지 않음

공간복잡도보다는 시간복잡도를 더 신경써야 함!!

---

방법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:     # alphabet_array 의 길이(26)만큼 아래 연산이 실행
        occurrence = 0                  # 대입 연산 1번 실행
        for char in string:             # string 의 길이(N)만큼 아래 연산이 실행
            if char == alphabet:        # 비교 연산 1번 실행
                occurrence += 1         # 대입 연산 1번 실행

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

    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 의 길이 X 대입 연산 1번

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

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

만큼의 시간이 필요!

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

위의 함수는 52N + 104 만큼의 시간이 걸렸다고 말할 수 있음

하지만 배수나 상수 등 숫자는 별 의미가 없으니까 제외하면

 

결론) N만큼의 시간이 걸렸다고 하면 됨!

 

 

방법2)

각 알파벳의 빈도수를 배열에 저장한 다음, 빈도수 중 가장 많은 알파벳의 인덱스 값을 반환

def find_max_occurred_alphabet(string):
    alphabet_occurrence_list = [0] * 26

    for char in string:                             # string 의 길이만큼 아래 연산이 실행
        if not char.isalpha():                      # 비교 연산 1번 실행
            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)):        # 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번 실행

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

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

2. 대입 연산 2번

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

만큼이 시간이 필요

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

3N + 106 만큼의 시간이 걸렸다 라고 할 수 있음

하지만 상수는 제외해도 되니까

 

결론) N 만큼의 시간이 필요하다라고 말할 수 있음

 

N의 길이	52N + 104	3N + 106	N^2
1	156	109	1
10	624	136	100
100	5304	406	10000
1000	52104	3106	1000000

52N+104든 3N+106이든 N^2에 비해서 아무것도 아니구나!!

 

 

 

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

공간을 희생해서라도 시간복잡도를 최대한 좋게 만드는 것을 고민해야한다