시간 복잡도
- 입력값과 문제해결시간과의 상관관계
- 입력값이 2배로 늘어났을 때 문제해결시간이 몇 배로 늘어나는 가?
- 입력값이 늘어도 시간이 적게 늘어나는 알고리즘이 좋은 알고리즘!
예시1
- 앞의 파트2에서 알고리즘 예제1 최댓값 찾기 방법1을 가지고 시간 복잡도를 판단해보기
for num in array:
for compare_num in array:
if num < compare_num:
break
else:
return num
- 각 줄이 실행되는 것이 1번의 연산이 된다고 생각하자
- array의 길이 X array의 길이 X 비교 연산 1번
만큼의 시간 필요.
array(입력값)의 길이는 보통 N으로 표현
N X N
N^2 만큼의 시간이 걸렸겠군!
- 입력값이란?
함수에서 크기가 변경될 수 있는 값
- N이 6인걸 알아도 N^2를 36이라 표현하지않고 N^2 수식으로 표현해야 N의 크기에 따른 시간의 상관관계라고 말할 수 있다. 즉 우리가 알고 싶은 것은 N^2라는 수식이지 36이라는 크기가 아니다
예시2
- 앞의 파트2에서 알고리즘 예제1 최댓값 찾기 방법2을 가지고 시간 복잡도를 판단해보기
max_num = array[0]
for num in array:
if num > max_num:
max_num = num
- 1.max_num 대입 연산 1번
2.array의 길이 * (비교 연산 1번 + 대입 연산 1번)
만큼의 시간 필요
1+ 2 X N
2N+1 만큼의 시간이 걸렸겠군!
예시1, 2 비교하기
| N의 길이 | N^2 | 2N+1 |
|---|
| 1 | 1 | 3 |
| 10 | 100 | 21 |
| 100 | 10000 | 201 |
| 1000 | 1000000 | 2001 |
| 10000 | 100000000 | 20001 |
- N, N^2는 N이 커질수록 큰 차이가 난다.
- N의 지수를 먼저 비교하자
- 상수는 큰 영향이 없으니 신경쓰지말고 입력값에 비례해 어느 정도로 증가하는지만 파악하기
- 2N+1의 연산량이 나오면 N 만큼의 연산량이 필요하다고 요약해서 말하면 되고
- N^2의 연산량이 나오면 N^2 만큼의 연산량이 필요하다고
- 상수의 연산량이 나오면 1 만큼의 연산량이 필요하다 말하면 된다.
공간 복잡도
- 입력값과 문제해결을 위해 필요한 공간의 양과의 상관관계
- 입력값이 2배로 늘어났을 때 문제해결에 필요한 공간의 양은 몇 배로 늘어나는 가?
- 입력값이 늘어도 필요한 공간이 적게 늘어나는 알고리즘이 좋은 알고리즘!
- 그러나 시간과 공간은 반비례적이라 공간보단 시간 복잡도에 초점을 맞춰 신경쓰자. 지금은 대용량시대니까
예시3
- 앞의 파트2에서 알고리즘 예제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", "x", "y", "z"]
max_occurrence = 0
max_alphabet = alphabet_array[0]
for alphabet in alphabet_array:
occurrence = 0
- 저장하는 데이터의 양이 1개의 공간을 사용한다.
- alphabet_array 의 길이 = 26
max_occurrence, max_alphabet, occurrence 변수 = 3
29
이 함수는 29 만큼의 공간이 사용되었군
예시4
- 앞의 파트2에서 알고리즘 예제2 최빈값 찾기 방법2을 가지고 공간 복잡도를 판단해보기
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(26):
alphabet_occurrence = alphabet_occurrence_list[index]
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
이 함수는 30 만큼의 공간이 사용되었군!
예시3, 4의 시간 복잡도
방법1
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 = number
- 1.alphabet_array 의 길이 X 대입 연산 1번
2.alphabet_array 의 길이 X string의 길이 X (비교 연산 1번 + 대입 연산 1번)
3.alphabet_array 의 길이 X (비교 연산 1번 + 대입 연산 2번)
- string의 길이는 보통 N으로 표현
26 X (1+2N+3) = 52N + 104
이 함수는 52N + 104 만큼의 시간이 걸렸겠군!
하지만 다른 상수의 시간에 대한 연산은 계산하지않아도 된다고 했으니 N 만큼의 시간이 필요하다고 이해하기
방법2
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
- 1.string의 길이 X (비교 연산 1번 + 대입 연산 2번)
2.대입 연산 2번
3.alphabet_array 의 길이 X (비교 연산 1번 + 대입 연산 3번)
N X (1+2) + 2 + 26 X ( 1+3 ) = 3N + 106
이 함수는 3N + 106 만큼의 시간이 걸렸겠군
상수를 계산하지않으면 N 만큼의 시간이 필요한 것이다.
예시3, 4 비교하기
| N의 길이 | 52N+104 | 3N+106 | N^2 |
|---|
| 1 | 156 | 3 | 1 |
| 10 | 624 | 21 | 100 |
| 100 | 5304 | 201 | 10000 |
| 1000 | 52104 | 2001 | 1000000 |
| 10000 | 520104 | 20001 | 100000000 |
- 52N + 104, 3N + 106 는 N^2에 비해 큰 수가 아니다.
- 공간 복잡도보다는 시간 복잡도를 더 신경 써야한다.
