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

<알고리즘 이란?>

▷어떠한 문제를 해결하기 위한 과정, 방법

좋은 알고리즘을 만들기 위해서는,  단순 문제 해결을 넘어,

‘더 효율적으로 문제를 해결하는’ 알고리즘을

만들도록 노력해야 한다.

<좋은 코드(알고리즘)의 기준>

 

1. 시간 

2. 공간(컴퓨터의 저장공간-메모리) 으로 평가.

 

시간이 좀 더 중요하다.

공간은 비용을 들여서 늘릴 수 있으니.

 

좋은 알고리즘을 평가하기 위해서는 빅오 표기법 (Big - o)이라는 것을 사용한다.

(빅 오 표기법이란?▷ https://developer-sowoo.tistory.com/10?category=1191269)

빅 오 표기법으로는 시간 복잡도, 공간 복잡도를 나타낼 수 있다.

 

시간 복잡도:

데이터가 많아질수록 걸리는 시간이 얼마나 급격히 증가하는지 확인하는 척도

시간복잡도가 작을수록 좋은 알고리즘(=시간이 적게 걸린다, 더 빠른 알고리즘)

 

공간 복잡도:

프로그램을 실행시킨 후 완료하는 데 필요로 하는 자원 공간의 양이다

 

 

 

1. 시간복잡도(시간을 고려할 때)

 

각 프로그램별 작동에 걸리는 시간을 측정(x)

☞because 같은 알고리즘이라도 구동시키는 컴퓨터의 종류(사양),

프로그래밍 언어 종류 등에 따라 걸리는 시간이 다를 수 있기 때문에

 

그렇다면 어떻게 걸리는 시간을 평가하는가?

 

-> 시간 복잡도 (Time Complexity) 사용

(Big-O notation 으로 표기)

 

자료개수│알고리즘 종류	알고리즘 A	알고리즘 B
10개	10초	1초
100개	100초	2초
1,000개	1,000초	3초

알고리즘B 가 더 빠르다

알고리즘B 가 더 적은 시간을 요구한다

알고리즘B 가 더 좋다

알고리즘은 input 값에 따라 소요시간이 결정된다.

보통 input 값이 클수록, 소요시간이 증가한다

 

 

2. 공간복잡도(알고리즘이 사용하는 메모리양)

 

공간복잡도도 시간복잡도처럼 input된 데이터에 따라 결정이 된다.

입력된 데이터에 따라 나온 결과물의 상태를 보고 Big-O notation 으로 표기한다

 

예)

def add_up_list_element(list_1)

	result = 0

	for i in list_1:

	result += list_1[i]

	return result

 

결과물(result)에 총 합의 결과 1가지만 들어있으므로 공간 복잡도가 1이지만,(가정)

but, 시간복잡도는 for 문 때문에 list안의 요소 개수에 따라 결정이 된다.