[알고리즘] 정리 - 알고리즘 평가법

코드잇 강의를 듣고 정리한 알고리즘 내용 입니다.

 

---

1. 알고리즘 평가의 기준

1) 시간복잡도 : 얼마나 빠르게 실행되는지

2) 공간복잡도 :  얼마나 많은 공간이 필요한지

 

 

2. 복잡도 계산과 관련해서 알고 있으면 좋은 수학 개념

1) 거듭제곱 

 

2) 로그

 

3) 1~n 까지의 합

 

 

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

1) 점근 표기법

- 원 함수를 단순화시켜 최고차항의 차수만 고려하는 것

- ex) 원 함수 : 2(n^2) + 8n + 157 / 점근 표기법 : O(n^2)

 

2) 점근 표기법의 의미

- n의 차수가 클수록 시간이 많이 소요된다는 것을 알 수 있음

- 컴퓨터의 사양이 아무리 좋아도, 아무리 빠른 언어로 코딩을 해도 알고리즘이 별로면 한계가 있다는 것을 알려줌

 

 

4. 알고리즘 평가 주의 사항

1) 코드의 모든 줄은 O(1)이 아니다.

- 인풋 크기과 상관 없이 실행되는 코드만 O(1), 다른 코드는 시간 복잡도 따져봐야 함

- sorted, sort 메소드 실행 시 O(n lg n)의 정렬 이루어짐

- 리스트에서 in 키워드 사용 시 O(n)의 선형 탐색 이루어짐

 

2) List Operations 시간 복잡도 

- 슬라이싱(변수명[a:b]) : O(b-a)

- 인덱싱 : O(1)

- len() : O(1)

- append() : O(1)

- insert() :O(n)

- del : O(n)

- reverse() : O(n)

- min/max : O(n)

 

2) Dictionary Operations 시간 복잡도 

- 값 찾기(변수명[key]) : O(1)

- 값 넣어주기/덮어쓰기(변수명[key] = value) : O(1)

- del : O(1)

 

 

5.  주요 시간 복잡도 Case

1) O(1) 

- 인풋의 크기가 소요 시간에 영향이 없음

def example_O1(lst) :
	print(lst[0])

example_O1([2,3]) # 출력 결과 : 2 
example_O1([2, 3, 5, 7, 9, 11, 15]) # 출력 결과 : 2 

 

2) O(n) 

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

# case1
def example_On(lst) :
	for i in range(len(lst)):
    	print(lst[i])
        
# case2
def example_On(lst) :
	for i in range(len(lst) // 2):
    	print(lst[i])
        
# case3
def example_On(lst) :
	for i in range(len(lst)):
    	print(lst[i])
        
	for i in range(len(lst)):
    	print(lst[i])
        
	for i in range(len(lst)):
    	print(lst[i])

 

3) O(n^2) 

- 반복문이 중첩되어 있고, 두 개의 반복문 모두 인풋의 크기에 비례할 경우 O(n^2)

def example_On2(lst):
	for i in range(len(lst)) :
    	for j in range(len(lst)) :
        	print(lst[j], lst[j])

 

 

4) O(n^3) 

- 반복문이 세 번 중첩되어 있고, 세 개 모두 인풋의 크기에 비례할 경우 O(n^3)

def example_On2(lst):
	for i in range(len(lst)) :
    	for j in range(len(lst)) :
        	for k in range(len(lst)) :
            	print(lst[i], lst[j], lst[k])

 

5) O(lg n) 

#case 1 : 2의 거듭제곱을 출력하는 함수
def example_Olgn(n):
	i = 1
    while i < n :
    	print(i)
        i = i * 2

#case 2 : 2의 거듭제곱을 출력하는 함수
def example_Olgn(n):
	i = 1
    while i < n :
    	print(i)
        i = i / 2

 

6) O(n lg n) 

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

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

 

 

6.  주요 공간 복잡도 Case

1) O(1) 

- 인풋의 크기가 메모리 공간에 영향이 없음

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

 

 

2) O(n) 

def example_On(lst) :
	my_list = lst[::2]
    return my_list

# lst의 짝수 인덱스의 값들이 복사돼서 my_list에 들어감
# 약 n/2개의 값이 들어가니 (1/2)n이므로 공간 복잡도는 O(n)

 

3) O(n^2) 

def example_On2(lst) :
	products = []
    for a in lst :
    	for b in lst :
        	products.append(a * b)

    return max(products)

# products에는 lst에서 가능한 모든 조합의 곱이 들어감
# 총 n^2 값이 들어가기 때문에 공간 복잡도는 O(n^2)