내일배움캠프 AI - TIL 53

 

❤️‍🔥TIL : Today I Learned❤️‍🔥
그날그날 내가 공부한 것을 정리하는 것

 

 

내일배움캠프 AI트랙 53day

 

 

 오늘 배운 내용 - 알고리즘 효율성

월,화 알고리즘을 풀고 테스트 해봤는데 나는 정확성 보다는 효율성에서 RuntimeError가 나면서 문제가 생겼던 부분들이 몇번 있었던 것 같다.

어제는 안그래도 고민하느라 지끈거려서 차마 확인하지 못했떤 Runtime error와, 시간 복잡도에 대해서 오늘은 알아보았다.

 

Runtime Error

말그래로 Run-time 실행시에 도중에 일어나는 에러.

대부분 프로그램을 짤때의 문법적으로 오류는 없어도 설계 미숙으로 일어나며 발생되는 조건은 매우 다양하지만 대표적으로는 조건문을 잘못써서 반복문을 빠져나오지 못하는 무한루프나 ZeroDivisionError 등 같은 경우가 있다.

 

내 경우에는 알고리즘 문제를 풀때 무한루프일 경우보다는 시간이 초과되는 경우가 많았다.

 

Time Complexity (시간 복잡도)

특정한 크기의 입력에 대해 알고리즘이 걸리는 시간을 의미한다.

같은 결과를 가져오는 프로그래밍이라도 어떻게 설계하고 작성하느냐에 따라서 소모하는 메모리, 걸리는 시간 등 효율성이 달라진다.

당연하게도 적게 걸릴 수록 좋은 소스이기 때문에 더 효율적인 알고리즘을 구성하기 위해서 시간 복잡도 측면을 고려해야된다.

복잡도에는 크게 두가지가 있다.
1. 시간복잡도(Time Complexity) : 작성한 프로그램이 얼마나 많은 공간(메모리)를 차지하는가
2. 공간복잡도(Space Complexity) : 작성한 프로그램이 얼마나 많은 시간이 걸리는가
최근에 컴퓨터 성능의 발달로 인해 메모리의 여유공간이 충분해지면서 공간복잡도보다는 시간복잡도를 우선시하여 프로그램을 작성한다.

 

시간 복잡도를 표기하는 방법

시간복잡도는 아래 3가지 표기법으로 표현한다.

• Big-O(빅-오) ⇒ 상한 점근(최악)
• Big-θ(빅-세타) ⇒ 그 둘의 평균(평균)
• Big-Ω(빅-오메가) ⇒ 하한 점근(최상)

하지만, 평균의 경우는 기준이 모호하고, 최악의 경우를 고려하여 최대 얼마나 걸릴는지를 알고있으면 대비를 할 수 있어 시간 복잡도를 표기할때 빅오 표기법을 주로 사용한다. 

 

 Big-O 표기법

 

1. O(1) : 일정한 복잡도(constant complexity). 입력값이 증가하더라도 시간이 늘어나지 않는다.

function O_1_algorithm(arr,index):
	return arr[index]
    
arr = [1,2,3,4,5]
index = 1
result = O_1_algorithm(arr,index) # 출력값 2

• 예시 알고리즘에서 보았듯이 입력값의 크기가 아무리 커져도 즉시 출력값 반환가능하다.

 

 

2. O(n) : 선형 복잡도(linear complexity). 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것

function O_n_alogrithm(n):
	for i in range(n):
    	#  do something for 1 second

• 위의 예제 알고지름과 같이 입력값이 1 증가 할때마다 실행 코드가 1초씩 증가한다. 즉 입력값이 증가함에 따라 같은 비율로 걸리는 시간이 늘어나고 잇다.
• 만약 입력값이 증가할때마다 2초씩 걸린다고 하더라도 같은 비율로 일정하게 증가한다면 마찬가지로 O(n)으로 표기
    (입력값이 커질수록 계수의 의미가 퇴색되기 때문이다.)

 

 

 

3. O(log n) : 로그 복잡도(logarithmic complexity). Big-O표기법중 O(1) 다음으로 빠른 시간 복잡도

 

4. O(n2) : 2차 복잡도(quadratic complexity). 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는것

function O_quadratic_algorithm(n):
	for i in range(n):
    		for j in range(n):
        		# do something for 1 second

• 위의 예제 알고지름과 같이 입력값이 1 증가 할때마다 실행 코드가 n초씩 증가한다. 
• 주로 반복문을 여러개 중첩해서 사용할 때가 이러한 경우이다.
• O(n)처럼 여러개 중첩되어도 지수가 주는 영향력이 퇴색되어서 동일하게 표현한다.

 

 

5. O(2n) :기하급수적 복잡도(exponential complexity). Big-O 표기법 중 가장 느린 시간 복잡도.

function fibonacci(n):
	if (n <= 1)
    	return 1
    return fibonacci(n-1) + fibonacci(n-2)

• 구현한 알고리즘의 시간 복잡도가 O(2n)이라면 다른 접근 방식을 고민해 보는 것이 좋다.
• 재귀로 구현하는 피보나치 수열은 O(2n)의 시간 복잡도를 가진 대표적인 알고리즘이다.
  n을 40으로 두어도 수초가 걸리는 것을 확인할 수 있으며, n이 100 이상이면 평생 결과를 반환받지 못할 수도 있다.

 

정리

알고리즘 문제를 풀다보면 사실 문제를 풀기에 급급하다보니 굴러는 가지만 효율이 최악으로 가는 경우들이 많다.

물론 문제의 정답을 찾는것이 가장 중요하지만, 이제는 가장 좋은 방법 이라는 것에 대해서 고민을 가져야 된다고 생각이 든다.