xodn158   2년 전

제가 책을 읽다가 이해안되는 부분이 있어서 설명좀 해드릴 수 있나요?

====

두 개의 함수 f(n)과 g(n)이 주어졌을 때, 모든  n >= n0 에 대해 |f(n) | <= c|g(n)| 을 만족하는 2개의 상수 c와 n0가 존재한다면 f(n) = O(g(n))입니다.

===

빅 오 표기법에서 n항에 붙는 계수는 1로 보아서 생략한다. 까지는 이해했습니다. 그런데 정의를 보니까 이해를 전혀 못하겠습니다.


jh05013   2년 전

우선 c가 사용되는 이유는 "계수를 생략"하기 위함입니다. 예를 들어 f(n)이 대충 3.4n이라면 c=4 정도로 잡으면 되겠죠.

그런데 비효율적인 알고리즘이라도 n이 작을 때는 오히려 빨리 돌아갈 수 있습니다. 예를 들어, 효율적인 알고리즘이 너무 무거워서 기본적인 설정을 하는 데 걸리는 시간이 그냥 바로 비효율적인 알고리즘을 돌리는 시간보다 오래 걸리는 경우가 그렇습니다. 그래서 알고리즘의 효율성을 따지려면 n이 충분히 큰 수여야 의미가 있고, 그래서 n >= n0 조건이 사용됩니다.

댓글을 작성하려면 로그인해야 합니다.