👩🏼‍💻TIL : 10. 시간복잡도(Time Complexity)

00. 시간복잡도란?

어떤 알고리즘이 빠른지 어떻게 판단할 수 있을까? 각 알고리즘을 돌려서 해볼 수도 있지만, 그렇게 되면 외부적(컴퓨터 사양 등) 다양한 외부환경의 영향을 받는다. 시간복잡도는 데이터가 많아질수록 걸리는 시간이 얼마나 급격히 증가하는가를 나타내는 개념이다. 아래 표와 같은 경우 첫번째 알고리즘보다 두번째 알고리즘이 시간복잡도가 더 크다 라고 할 수 있다. 

 

 

	알고리즘A	알고리즘
10개	10초	10초
20개	20초	40초
100개	100초	10000초
	(시간 복잡도가 작다)	(시간 복잡도가 크다)

 

01. 점근 표기법(Big-O Notation)

점근 표기법에서 n은 인풋 크기를 나타낼 때 가장 흔히 사용되는 문자일 뿐 별다른 의미는 없다. 인풋 리스트의 크기를 x라고 부르기로 하면O(lg x), O(x) 등의 표기를 할 수 있다. 트리나 그래프의 경우 선형적이지 않기 때문에 꼭짓점과 변을 사용하여 O(V+E)로 계산하게 된다. 

 

n	O(1)	O(n)	O(n^2)	O(n^3)
100	1초	1초	1초	1초
200	1초	2초	4초	8초
1000	1초	10초	100초	1000초
10000	1초	100초	1000초	1000000초

 

 점근 표기법의 핵심은 n이 크다고 가정하는 것이다. n이 별로 크지 않으면, 안 좋은 알고리즘을 써도 문제 없다. 그래서 다른것은 무시해도 된다.

 

소요시간	점근표기법
20n + 40	O(n)
2n^2 + 8n + 157	O(n^2)
5n^3 + 100n^2 + 75	O(n^3)
20lgn + 60	O(lg n)

 

	선형 탐색	이진탐색
최고의 경우	O(1)	O(1)
최악의 경우	O(n)	O(lg n)

 

02. 시간 복잡도

 (0) O(1), O(ℓg n), O(n), O(n ℓg n), O(n^2), O(n^3)를 정리해보자

 

 (1) O(1)

  O(1)은 인풋의 크기가 소요시간에 영향이 없다는 뜻이다. 밑의 코드는 print_fist에 요소를 다르게 하여 print_fist라는 함수에 넣어주는데, 두 경우 어차피 맨 앞에 있는 요소를 받아오는 것 뿐이니 걸리는 시간은 거의 똑같다. (반복문이 없으면 대체로 O(1)이다.)

def print_first(my_list):
	print(my_list[0])
    
print_first([2, 3])
print_first([2,3,4,5,6,7,8,9,0,1,11,1,2,3,4,5,])

 

 (2) O(n)

  - 반복문이 있고, 반복되는 횟수의 인풋의 크기가 비례하면 일반적으로 O(n)이다.

  - Case2의 경우에도 n/2번 반복한다면 O(/12 n) 이지만 점근표기법으로 보면 O(n)이라고 할 수 있다.

#Case1
def print_each(arr):
	for i in range(len(arr)):
    		print(arr[i])

#Case2
def print_half(arr):
	for i in range(len(arr) // 2):
    		print(arr[i])
        
#Case3
def print_three_times(arr):
	for i in range(len(arr)):
    		print(arr[i])
	for i in range(len(arr)):
    		print(arr[i])
	for i in range(len(arr)):
    		print(arr[i])

 

 (3) O(n^2)

   두 반복문 다 인풋 크기에 비례하는 경우 O(n^2)이다.

def print_arr(arr):
	for i in range(len(arr)):
    		for j in range(len(arr)):
        		print(arr[i], arr[j])

 

 (4) O(n^3)

def print_arr(arr):
	for i in range(len(arr)):
    		for j in range(len(arr)):
            		for k in range(len(arr)):
        				print(arr[i], arr[j], arr[k])

 

(5) O(lg n)

def print_arr(n):
	i = 1
    while i < n:
    	print(i)
        i = i * 2

 

 (6) O(n lg n)

def print_powers_of_two_repeatedly(n):
    i = 1
    while i < n: # 반복횟수: lg n에 비례
        for j in range(n): # 반복횟수: n에 비례
            print(i, j)
        i = i * 2

 

 

03. List Operations

Operaiton	Code	Average Case
인덱싱	my_list[index]	O(1)
정렬	my_list.sort() sorted(my_lsit)	O(n lg n)
뒤집기	my_list.reverse()	O(n)
탐색	element in my_list	O(n)
끝에 요소 추가	my_list.append(element)	O(1)
중간 요소 추가	my_list.insert(index, element)	O(n)
삭제	del my_list[index]	O(1)
최댓값 최솟값 찾기	min(my_list) max(my_list)	O(n)
길이구하기	len(my_list)	O(1)
슬라이싱	my_list(a:b)	O(b - a)

 

 

04. Dictionary Operations

operation	Code	Average Case
값 찾기	my_dict[key]	O(1)
값 넣어주기 /  덮어쓰기	my_dict[key] = value	O(1)
값 삭제	del my_dict[key]	O(1)

 

05. 파이썬의 시간복잡도

 (1) type : O(1)

 (2) max, min : O(n)

 (3) str : O(log n) /  O(d) // d는 자리수

 (4) append, insert, del, index, reverse : O(1)

 (6) sort, sorted : O(n lg n)

 (7) slicing : O(b - a)

 (8) len : O(1)

06. 공간복잡도(Space Complexity)

공간 복잡도는 인풋 크기에 비례해서 알고리즘이 상요한느 메모리 공간을 나타낸다.

 

 (1) O(1) 

  파라미터 a, b, c가 차지하는 공간을 제외하면 추가적으로 변수 result가 공간을 차지한다. result가 차지하는 메모리 공간은 인풋과 무관하기 때문에 함수 product의 공간 복잡도는 O(1)이다.

def product(a, b, c):
	result = a * b * c
    return result

 

(2) O(n)

def get_every(arr):
	every_other = arr[::2]
    return every_other

 

(3) O(n^3)

def largest(list):
	products = []
    for a in list:
    	for b in my_list:
        	products.append(a * b)
	return max(products)