입력값과 문제를 해결하는 데 걸리는 공간과의 상관관계를 말한다.
입력값이 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개의 공간을 사용합니다
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
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번)
만큼의 시간이 필요합니다. 여기서 string 의 길이는 보통 N이라고 표현한다. 그러면 위의 시간을 다음과 같이 표현할 수 있다
26(1 + 2N + 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번 실행
- 위에서 연산된 것들을 더해보면,
1. string의 길이 X (비교 연산 1번 + 대입 연산 2번)
2. 대입 연산 2번
3. alphabet_array 의 길이 X (비교 연산 1번 + 대입 연산 3번)
만큼의 시간이 필요합니다. 여기서 string 의 길이는 보통 N이라고 표현한다. 그러면 위의 시간을 다음과 같이 표현할 수 있다.
>
N (1 + 2) + 2 + 26 (1 + 3) = 3N + 106
이제 이 함수는 만큼의 시간이 걸렸겠구나! 생각할 수 있다.