점근적상한

시간복잡도의 점근적 표기법

알고리즘의 효율성은 주로 시간복잡도(time complexity)로 표기한다. 시간복잡도는 알고리즘이 수행하는 기본적인 연산 횟수를 입력 크기에 대한 함수로 표현한다. 시간복잡도를 표현하는 방법인 점근적 표기법과 최Big-O 표기법에 관해 간략하게 알아보자 점근적 표기법 입력 크기 n이 무한대로 커질때, 다른 어떤 함수로 근사되는지를 간단히 표현하기 위해 사용되는 표기법 점근적 상한 최악의 수행시간을 나타내기 위한 표기법이다. 주어진 알고리즘이 아무리 나빠도 비교하는 함수와 같거나 좋다. 점근적 하한 최선의 수행시간을 나타내기 위한 표기법이다. 점근적 상하한 복잡도의 상한과 하한이 동시에 적용되는 경우를 나타낸다. Big-O notation $ \mathrm{O}$ -표기는 복잡도의 점근적 상한을 나타낸..