접근 표기법 (Big-O Notation). 빅오 표기법

알고리즘의 크기를 

인풋크기가 커질수록 알고리즘 실행시간이 오래걸림

알고리즘의 소요시간을 인풋크기에 대한 수식으로 나타냄.

 

하지만 방식에 따라 알고리즘 소요시간이 달리 계산됨

이에 대한 방안으로 나타난 것이 점금 표기법(빅오)

점근 표기법의 핵심은 n이 엄청크다는 가정하에 진행해야한다는 것!

n이 엄청 커졌을 때, 가장 큰 n을 제외한 식의 값은 굉장히 작기에 무시하는 것

위를 빅오 표기법으로 나타내면 하단과 같다

빅오 표기법당 시간 그래프

컴퓨터 성능이 좋아도

빠른 프로그래밍 언어를 써도

알고리즘이 별로면 한계가 존재한다.

예시

선형탐색 베스트

선형탐색 최악

이진 탐색 베스트

이진탐색 최악