[Algorithm] 시간 복잡도와 공간 복잡도

 

 

 

 

'알고리즘을 효율적을 짠다 = 시간과 공간을 최소화한다'

 

알고리즘의 효율성을 판단할 때, 시간 복잡도(Time complexity)와 공간 복잡도(Space complexity)를 따진다.

백준, 프로그래머스에서도 알고리즘을 평가할 때 시간과 메모리 제한을 두는 것도 다 이런 이유에서다.

 

 

 

 

---

 

 

 

 

 

 

시간 복잡도(Time complexity) 개념와 예시

---

 

'입력값의 증가에 대한 연산 횟수 증가분'

 

시간 복잡도는 그저 실행 시간을 측정하는 것이 아니다. 실행 시간은 측정을 위한 프로그램이 필요할뿐더러 수행 환경에 따라 실행 시간이 달라질 수 있다. 이에 따라 입력값이 증가함에 따라 연산 횟수가 어떤 비율로 증가하는가에 초점을 두고 시간 복잡도를 측정한다. 

시간 복잡도는 Worst Case, 즉 가장 최악으로 시간이 걸릴 경우를 계산하는 Big-O Notation을 쓴다.

 

 

Big-O Notation 표기법

1) 점근적 상한선(Asymptotic upper bound)

2) 최대 차수의 계수와 나머지 차수의 항을 모두 제외

3) 상수 제거, 1로 취급

 

 

 

 

O(1) - 입력 자료의 수(n)에 관계없이 일정한 실행 시간을 갖는다. ex) 배열에서 특정 인덱스 찾기

list = [a, b, c, d, e]
list[0]

 

 

 

O(logn) - 초반엔 빠르지만 후반부 갈수록 시간 증가한다. ex) 이진 탐색 

def binary_search(target, start, end, data):
	if start > end :
    	return None
	
    mid = (start + end) // 2
    
    if data[mid] == target:
    	return mid
	elif data[mid] > target:
    	end = mid - 1
    else:
    	start = mid + 1
    
    return binary_search(target, start, end, data)


if __name__ == '__main__':
	li = [i for i in range(1, 100)]
    target = 25
    idx = binary_search(target, 1, 99, li)
    
    print(li)
    print(idx)

 

 

 

O(n) - 입력 자료의 크기가 n일 경우 n번만큼의 수행 시간을 가진다. ex) 연결 리스트 순회, 최댓값 찾기

list = [1,2,3,4,5]
min(list) // max(list)

 

 

 

O(2^n) - '지수적 증가'는 엄청난 연산 횟수 증가를 야기한다. ex) 피보나치수열 

def fibo(n: int) -> int:
    if n <= 2:
        return 1
    return fibo(n - 1) + fibo(n - 2)

 

 

 

O(n^2) - 주로 2중 for loop를 사용하여 조합 가능한 모든 쌍을 대상으로 하는 경우. ex) 퀵 정렬

li = [a, b, c, d, e,, f]

def for_for(li):
	for i in li:
    	for a in li:
        	print(f'{i}/{a}')

 

 

 

 

 

 

 

 

공간 복잡도(Space complexity) 개념과 예시

---

입력값에 비례한 알고리즘이 사용하는 메모리 공간

 

 

공간 복잡도는 보조 공간 + 입력 공간을 합친 개념이지만, 실제론 알고리즘이 실행되는 동안 사용하는 임시 공간인 보조 공간만을 고려한다.

 

시간과 공간은 반비례적 경향이 있어, 시간 복잡도 위주로 판단한다.

 

 

 

O(1) 공간 복잡도

def solution(a, b):
	result = a + b
    	return result

 

 

O(n) 공간 복잡도

def solution(li):
	slice = li[2:len(li)]
    	return slice

리스트 길이를 n이라고 한다면, n의 크기에 따라 비례적으로 메모리 크기가 증가한다.

 

 

 

O(n^2) 공간 복잡도

def solution(li):
	products = []
    	for a in li:
    		for i in li:
        		products.append(a*b)
    	return max(products)

길이가 n인 리스트에 for 문을 중첩하여 값을 생성했다. 그에 따라 products 리스트의 값은 n^2가 되면서 메모리 또한 그만큼 잡아먹게 된다.

 

 

 

 

시간 복잡도와 공간 복잡도를 배웠다. 

이제부턴 알고리즘 문제를 풀 때, 복잡도를 생각해보면서 효율적인 코드를 짜려 노력해보자.