알고리즘

빅오 표기법이란? (About Big-O)

빅오 표기법 (Big-O) 빅오 표기법이란 ? 연산의 횟수를 대략 표기한 것 설명하기 전에 시간 복잡도의 정의를 알아야 한다. 시간 복잡도는 어떤 알고리즘을 이루고 있는 연산들이 몇 번이나 수행되는지를 시간으로 설명하는 계산 복잡도를 의미한다. 그리고 이러한 계산 복잡도를 표기하는 방법중 하나가 빅오 표기법이다. 예를 들어보자 분모가 계속해서 커지는 분수를 생각해보면 쉽다. 1/∞ 은 결국 0에 수렴하고 분모가 어떤 상수가 와도 결국엔 0으로 수렴한다. 빅오 표기법도 같다. 4n^2 + 3n +4 이 수식에서 n이 무한대로 커진다고 생각해보자. 일단 상수항 4는 의미가 없어진다. 그리고 3n도 4n^2이 엄청나게 커지면 의미가 없으므로 제외한다. 결국 위 식에서 남는 것은 최고차항인 n^2만 남는다. 그..