시간 복잡도
- 시간 복잡도란?
- 반에 있는 사람들이 N명이라고 한다면B 방식은 N^2 만큼의 연산이 필요하다고 할게요.
- 💡 시간복잡도는 입력값과 문제를 해결하는 데 걸리는 시간과의 상관관계를 말합니다!
- 입력값이 2배로 늘어났을 때 문제를 해결하는 데 걸리는 시간은 몇 배로 늘어나는지를 보는 것이죠.
- 우리는 시간이 적게 걸리는 알고리즘을 좋아하니 입력값이 늘어나도 걸리는 시간이 덜 늘어나는 알고리즘이 좋은 알고리즘이겠죠?
- N 이 예를 들어서 30이라면 A 방식은 30번, B 방식은 900 번의 연산이 필요하겠죠
- A 방식은 N 번 만큼의 연산이 필요하고
- 예를 들어서 내가 반에 있는 사람들 중에서 가장 이성에게 호감이 높은 사람을 뽑는다고 해볼게요.
“입력값에 비해 얼마나 일을 수행해야 하는가?”
- 1) 최댓값 찾기 알고리즘의 시간 복잡도 판단해보기
- 첫 번째 방법
- 이 해결 방법은 각 숫자마다 모든 다른 숫자와 비교해서 최대값인지 확인합니다. 만약 다른 모든 값보다 크다면 반복문을 중단합니다.
- 이 함수가 시간이 얼마나 걸리는지 어떻게 분석할 수 있을까요?
- 바로, 각 줄이 실행되는 걸 1번의 연산이 된다고 생각하고 계산하시면 됩니다. 아래와 같이 계산할 수 있습니다.
- 위에서 연산된 것들을 더해보면
- array의 길이 X 비교 연산 1번
- 그러면 우리는 이제 이 함수는 2* N^2 + N 만큼의 시간이 걸렸겠구나! 라고 말할 수 있습니다.
- Q. 선생님 여기서 입력값이 뭔가요?
- A. 함수에서 크기가 변경될 수 있는 값이라고 보시면 됩니다! 배열을 받고 있으니 이 함수에서는 배열이 입력값입니다.
- Q. 선생님 그러면 여기서 N 이 6이니까, 78이라고 말하면 안되나요?
- A. N 의 크기에 따른 시간의 상관관계를 시간복잡도라고 하는 것이라 수식으로 표현하셔야 합니다!
def find_max_num(array):
for number in array:
is_max_num = True
for compare_number in array:
if number < compare_number:
is_max_num = False
if is_max_num:
return number
print("정답 = 6 / 현재 풀이 값 = ", find_max_num([3, 5, 6, 1, 2, 4]))
print("정답 = 6 / 현재 풀이 값 = ", find_max_num([6, 6, 6]))
print("정답 = 1888 / 현재 풀이 값 = ", find_max_num([6, 9, 2, 7, 1888]))
- 2) 최댓값 찾기 알고리즘의 시간 복잡도 판단해보기
for number in array: # array 의 길이만큼 아래 연산이 실행
for compare_number in array: # array 의 길이만큼 아래 연산이 실행
if number < compare_number: # 비교 연산 1번 실행
is_max_num = False # 대입 연산 1번 실행
if is_max_num: # 비교 연산 1번 실행
return number
공간 복잡도
- 입력값과 문제를 해결하는 데 걸리는 공간과의 상관관계를 말합니다!
- 입력값이 2배로 늘어났을 때 문제를 해결하는 데 걸리는 공간은 몇 배로 늘어나는지를 보는 것이죠.
- 우리는 공간이 적게 걸리는 알고리즘을 좋아하니 입력값이 늘어나도 걸리는 공간이 덜 늘어나는 알고리즘이 좋은 알고리즘이겠죠?
- 저장하는 데이터 양이 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", "w", "x", "y", "z"]
def find_max_occurred_alphabet(string):
max_occurrence = 0 # 1개의 공간을 사용
max_alphabet = alphabet_array[0] # 1개의 공간을 사용
for alphabet in alphabet_array:
occurrence = 0 # 1개의 공간을 사용
## 26 + 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 # 1개의 공간을 사용
max_alphabet_index = index # 1개의 공간을 사용
- 29나 30처럼 N과 상관이 없으면 공간복잡도는 성능에 영향을 주지 않는다. = 단순 대입연산만 늘어났으니
- 단 N에 따라서 공간복잡도가 기하급수적으로 늘어나면 고려해봄직하다.
출처 : 38군데 합격 비법, 2024 코딩테스트 필수 알고리즘