알고리즘의 시간 복잡도의 점근적 표기법

개요 어떠한 알고리즘의 실행 시간을 입력 크기 n에 따른 단위 연산 수로 정의한 것으로, n에 대한 함수로 표현할 수 있음. 동일한 문제에 대해 알고리즘 1은 n2의 시간 복잡도, 알고리즘 2는 n이라 하면 알고리즘 2가 무조건 효율적이다.

그러나, 알고리즘 1은 n^2, 알고리즘 2는 10000n이라 두면 무엇이 더 효율적인지는 n에 의존한다. n이 작은 경우 알고리즘 1이 더 효율적이며, n이 큰 경우 알고리즘 2가 더 효율적이다. 알고리즘의 점근적 복잡도 입력 크기 n의 값이 무한히(혹은 충분히) 큰 경우일 때 알고리즘의 복잡도 n의 값이 충분히 크다 가정하므로, 점근적 시간 복잡도는 최고차항의 차수가 지배한다.

점근적 복잡도로 따지는 경우, 위 예시에서 알고리즘 2가 더 효율적이라 할 수 있음 O (BIg - O) 표기법 알고리즘 복잡도의 점근적 상한을 표기함 정의: 어떤 알고리즘의 시간 복잡도를 g(n)이라 할 때, n > N인 모든 정수 n에 대해 항상 g(n) ≤ c *...