시간복잡도
: 입력값과 문제를 해결하는데 걸리는 시간의 상관관계
즉, 입력값이 두배로 늘어나면 문제를 해결하는데 걸리는 시간은 몇배로 늘어나는가를 보는 관계를 의미한다.
우리는 시간이 적게 걸리는 알고리즘을 좋아하니까 입력값이 늘어나도 문제 해결 시간이 많이 늘어나지 않는 알고리즘을 선호한다.
input = [3, 5, 6, 1, 2, 4]
def find_max_num(array):
for num in array:
for compare_num in array:
if num < compare_num:
break
else:
return num여기서
for num in array: # array 의 길이만큼 아래 연산이 실행
for compare_num in array: # array 의 길이만큼 아래 연산이 실행
if num < compare_num: # 비교 연산 1번 실행
break
else:
return num- array의 길이 X array의 길이 X 비교 연산 1번 만큼의 시간이 필요하다.
여기서 array(입력값)의 길이는 보통 N이라고 표현합니다. 그러면 위의 시간을 다음과 같이 표현할 수 있습니다.
N x N
따라서 위의 코드는 N2 만큼의 시간이 걸린 것이다.
❓
Q. 여기서 입력값이란?
A. 함수에서 크기가 변경될 수 있는 값
배열을 받고 있으니 이 함수에서는 배열이 입력값이다.
.
Q. 그러면 여기서 N 이 6이니까, 36이라고 말하면 안되나?
A. N 의 크기에 따른 시간의 상관관계를 시간복잡도라고 하는 것이라 수식으로 표현해야 한다.
def find_max_num(array):
max_num = array[0]
for num in array:
if num > max_num:
max_num = num
return max_num
result = find_max_num(input)
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]))max_num = array[0] # 연산 1번 실행for num in array: # array 의 길이만큼 아래 연산이 실행
if num > max_num: # 비교 연산 1번 실행
max_num = num # 대입 연산 1번 실행- max_num 대입 연산 1번
- array의 길이 X (비교 연산 1번 + 대입 연산 1번)
만큼의 시간이 필요하다. 첫 번째 방법에서 했던 것처럼 array 의 길이를 N이라고 하면, 다음과 같이 표현할 수 있다.
1 + 2 x N
그러면 걸리는 시간은 2N + 1
