시간과 공간
- 우리는 알고리즘을 통해 원하는 결과가 빨리 나오길 바라지만 컴퓨터의 저장공간(메모리)의 제약이 발생한다. 이에 좋은 알고리즘을 평가하기 위해서는 시공간을 기준으로 평가하게 된다.
시간 복잡도(Time Complexity)
- 컴퓨터 사양이나 사용한 프로그래밍 언어등 다양한 외부 환경으로 인해 프로그램이 들오가는 시간으로 알고리즘을 평가하기엔 어려움.
- 그래서 데이터가 많아질수록 걸리는 시간이 얼마나 급격히 증가하는지를 나타내는 '시간복잡도'를 이용
점근표기법(Big-O)
- 알고리즘의 효율성을 표현하는 방법
- n이 크다고 가정(n이 크지 않으면 안좋은 알고리즘이라도 문제없음=큰 차이가 없음)
- 절대적인 시간이 아닌 성장성을 봄
1. 인풋리스트의 길이와 알고리즘 소요시간을 비교
-
O(1)알고리즘: 인풋사이즈에 영향을 받지 않음
-
O(n)알고리즘: 인풋사이즈가 2배 → 걸리는 시간이 약 2배가 됨(인풋사이즈가 10배면 시간도 약 10배)
-
O(n²)알고리즘: 인풋사이즈 2배 → 걸리는시간 4배(2²)
n O(1) O(n) O(n²) O(n³) 100 1초 1초 1초 1초 200 1초 2초 4초 8초 1000 1초 10초 100초 1000초 10000 1초 100초 10000 1000000초 * n = 예) 인풋 리스트의 길이
여기서 O(1)은 인풋 크기와 상관없이 실행되는 코드! 그렇지 않은 코드는 시간 복잡도를 따져봐야 한다.
알고리즘 소요시간의 격차가 Big-O의 제곱 값이 커질수록 급격히 커지기 때문에 컴퓨터 사양이나 프로그래밍 언어가 아무리 좋다고 하더라도 알고리즘이 별로라면 한계가 생김 = 알고리즘은 중요하다!!
2. 선형탐색 알고리즘 평가
def linear_search(element, some_list):
i = 0 #O(1)
n = len(some_list) #O(1)
while i < n: #O(1)X반복횟수
if some_list[i] == element:
return i
i += 1
return -1 #O(1)1) while문을 한번 반복하여 값을 찾은 경우
O(1) + O(1) + O(1) + O(1) = O(4) = O(1)
* O(4)은 O(1)와 동일
2) 리스트에 찾는 값이 없는 경우
O(1) + O(1) + O(n) + O(1) = O(n+3) = O(1)
2. 이진탐색 알고리즘 평가
def binary_search(element, some_list):
start_index = 0 #O(1)
end_index = len(some_list) - 1 #O(1)
while start_index <= end_index: #O(1)X반복횟수
midpoint = (start_index + end_index) // 2
if some_list[midpoint] == element:
return midpoint
elif some_list[midpoint] > element:
end_index = midpoint - 1
else:
start_index = midpoint + 1
return None #O(1)1) while문을 한번 반복하여 값을 찾은 경우
O(1) + O(1) + O(1) + O(1) = O(4) = O(1)
* O(4)은 O(1)와 동일
2) 리스트에 찾는 값이 없는 경우
O(1) + O(1) + O(log n) + O(1) = O(log n) + 3 = O(log n)
* 이진탐색은 찾는 값의 범위가 절반씩 줄어드니 log사용
공간 복잡도(Space Complexity)
- 인풋 크기에 비례해서 알고리즘이 사용하는 메모리 공간
공간 복잡도도 점근표기법으로 표현 가능( = Big-O 표기법 사용가능)
파이썬에서의 시간복잡도
type: O(1)max,min: O(n)str: O(logn) or O(d) (파라미터가 n이고 n의 자릿수가 d일 때)append: O(1)insert: O(n)del: O(n)index: O(n)reverse: O(n)sort,sorted: O(n lg n)slicing(슬라이싱): O(b−a) (list[a:b] 일 때)len: O(1)
