TIL_20 : 알고리즘 평가법

JaHyeon Gu·2021년 7월 28일

TIL algorithm

Algorithm

목록 보기

2/7

🙄 평가의 두 기준

시간 : 빠르게 실행이 되어야 함
공간 : 적은 메모리, 용량을 차지해야 함

두 가지 중 한 가지를 고르자면 시간이 더 우선, 공간은 돈으로 늘릴 수 있기 때문 !!

🙄 시간 복잡도 (Time Complexity)

➡ 데이터가 많아질수록 걸리는 시간이 얼마가 급격히 증가하는가

인풋 크기	알고리즘 A	알고리즘 B
10개	10초	10초
20개	20초	40초
100개	100초	1000초
	시간 복잡도가 작다	시간 복잡도가 크다
	더 빠른 알고리즘	더 느린 알고리즘

🙄 점근 표기법 (Big-O Notation)

➡ 점근 표기 방법

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

점근 표기법은 $n$ 이 엄청 크다고 가정
$n$ 이 별로 크지 않으면, 안 좋은 알고리즘을 써도 문제 없기 때문

➡ 절대적인 시간이 아닌 성장성을 나타내는 것

➡ 점근 표기법의 의미

$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초	10000초	1000000초

➡ 알고리즘의 중요성

오래된 컴퓨터로 $O(1)$ 알고리즘을, 최신 컴퓨터로 $O(n^3)$ 알고리즘을 돌려보자

$n$	$O(1)$	$O(n)$	$O(n^2)$	$O(n^3)$
100	10초	1초	0.1초	0.01초
200	10초	2초	0.4초	0.08초
1000	10초	10초	10초	10초
10000	10초	100초	1000초	10000초

➡ 사양이 뛰어나도, 언어가 아무리 빨라도, 알고리즘이 나쁘면 한계

🙄 탐색 알고리즘 평가하기

➡ 선형 탐색

def linear_search(element, some_list):
	i = 0					# O(1)
    n = len(some_list)				# O(1)
    
    while i < n:				# O(1) * 반복횟수 n = O(n)        
    	if element == some_list[i]:		
            return i
        i += 1

return -1					# O(1)

# O(1) + O(1) + O(n) + O(1) = O(n+3) = O(n)

➡ 이진 탐색

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) * 반복횟수 lg n = O(lg n)
        mid = (start_index + end_index) // 2
        if some_list[mid] == element:
        	return mid
        elif element < some_list[mid]:
            end_index = mid - 1
        else:
            start_index = mid + 1
            
    return None					# O(1)

# O(1) + O(1) + O(lg n) + O(1) = O(lg n) + 3 = O(lg n)

🙄 공간 복잡도

➡ $O(1)$

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

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

➡ $O(n)$

def get_every_other(my_list):
	every_other = my_list[::2]
    return every_other

리스트 every_other에는 my_list의 짝수 인덱스의 값들이 복사돼서 들어감.
약 $O(n/2)$ 개

공간 복잡도 = $O(n)$

➡ $O(n^2)$

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