250929 Revision

알고리즘 성능을 수학적으로 나타내는 방법

정확한 실행 시간을 측정하는 것이 아니다
입력 크기를 N 이라고 가정, 성장의 속도

배열 요소가 10개일 때 1초, 100개 일때 10초 , 1000개 일때 100초가 걸린다
선형적으로 증가한다, O(N)


배열 요소가 10개일 때 1초, 100개일 때 100호, 1000개일 때 10000초
제곱으로 증가하고 있다 O(N^2)


BigO 는 성능의 '최고차항'만 남겨서 단순화 한 것
n-1 이라던지 /2 같은 상수 같은건 다 무시


for 를 3번 굴리는 알고리즘은 n^3 

 

 

O(n): 사람을 한 줄로 세워 차례대로 검사.

O(log n): 절반씩 줄여가며 검사.

O(2^n): 가능한 모든 경우를 일일이 다 시도.

 

 

지수 = "곱하기를 몇 번 반복했는가"

로그 = "곱하기 몇 번 해야 도달하는가"

빅오에서 지수는 주로 **조합 폭발(모든 경우 탐색)**에서 나타난다

 

 

쪼개기와 합치기의 반복

분할 ( Divide ) : 배열을 반으로 자르고

정복 ( Conquer ) : 쪼갠 배열을 재귀적으로 정렬

결합 ( Combine ) : 두 개의 정렬된 배열을 합병

 

시간 복잡도 , BigO 값

 

분할단계에서 로그값 Log² ( 이진수 로그 N )

Log N

 

합병단계, 각 단계마다 모든 N개 원소 다 보긴 해야한다

O(N)

 

N Log N

항상 안정적으로 이 속도를 가진다

최선의 케이스란 이미 정렬이 되어 있을때  N Log N

최악의 케이스 N Log N

평균 N Log N

 

 

DFS , BFS + 다익스트라 + A* 로 길 찾기
A*
목표지점까지 제일 빨리 가기 위해
현재까지의 비용 + 다음으로 갈 수 있는 경로 중 가장 빠른 경로를 판단하는걸 반복

F : Full Cost , G + H , 최종 걸릴 법한 값
G : 시작점 에서부터 현재까지 실제 이동 거리
H : 남은 거리 예측 ( Heuristic )