[C언어]36일차 - 빅오 표기법

성능에 대해서 알아야하는것들

예) 병합정렬을 사용해야 될지, 퀵 정렬을 사용해야 될지.

혹은 배열과 리스트 중 어느 것이 더 좋을지.

 

비디오 게임을 만들고 싶다면 그래프 알고리즘을 이용해서 사용자를 따라다리는 인공지능 시스템을 만들 수 있다.

KNN 알고리즘을 사용해 추천 시스템을 만드는 것을 배운다.

 

이진 탐색은 알고리즘이다. 

입력으로는 정렬된 원소 리스트를 받는다. 

이진 탐색 알고리즘은 리스트에 원하는 원소가 있으면 그 원소의 위치를 반환하고, 아니면 null 값을 반환한다.

 

1 - 100 사이에서 가장 적은 횟수의 추측으로 찾고자 하는 숫자를 알아내야 한다.

 

한 번 추측할 때마다 알아내야 하는 숫자보다 제시한 숫자가 더 작은지, 더 큰지, 맞는 숫자인지 알 수 있다.

 

 

이런 탐색을 단순 탐색 일고 한다. 한번 추측할 때마다 추측한 숫자 하나가 답이 아니라는 것을 알게될 뿐이다.

 

 

알고리즘의 실행 시간이 얼마가 걸리는지만 고려할것이 아니라, 리스트의 크기가 증가할 때 실행 시간이 어떻게 증가하는지도 파악해야 합니다.

 

빅오 표기법은 속도를 시간 단위로 세지 않는다.

빅오 표기법은 연산 횟수를 비교하기 위한 것이므로 수행해야 할 일이 많아질 때 알고리즘에 걸리는 시간이 어떤 식으로 증가하는지를 알 수 있습니다.

 

빅오표기 법은 최악의 경우에 대한 것이다.

 

 

알고리즘의 속도는 시간이 아니라 연산 횟수가 어떻게 증가하는지로 측정한다.

이렇게 입력하면 데이터의 크기가 늘어날 때 알고리즘의 실행 속도가 얼마나 증가하는지 알 수 있다.