빅오표기법 알고리즘 문제

질문

알고리즘 관련해서 빅오표기법을 공부하고 있는 대학생입니다.

예제를 보던 중에 5n^2 <= O(n^2) 임을 증명하라는 문제가 있어서
봤는데 예제 풀이에서는 c=6 , n0 = 1 일때 성립한다고 되어있는데요, 제가 직접 풀어본 결과 c=5 , n0=1 일때도 성립을 하더라구요.

제가 풀이한 것도 정답이 되는지에 대해 궁금합니다.

 

답변

안녕하세요. 빅오표기법에 대해 공부하고 계신다니 멋지십니다. 빅오표기법은 알고리즘의 시간 복잡도나 공간 복잡도를 나타내는 방법으로, 입력 크기가 충분히 큰 경우에 실행 시간이나 메모리 사용량의 상한을 표현합니다.

​

빅오표기법의 증명은 다음과 같은 방식으로 이루어집니다. f(n)이 O(g(n))이라고 하면, 어떤 상수 c와 n0가 존재해서 모든 n >= n0에 대해 f(n) <= c * g(n)이 성립한다는 것을 보여주면 됩니다.

​

문제에서 주어진 5n^2 <= O(n^2)을 증명하려면, 어떤 상수 c와 n0가 존재해서 모든 n >= n0에 대해 5n^2 <= c * n^2이 성립한다는 것을 보여주면 됩니다. 예제 풀이에서는 c=6 , n0 = 1 일때 성립한다고 되어있는데요, 이것은 맞습니다. 왜냐하면 모든 n >= 1에 대해 5n^2 <= 6 * n^2이 성립하기 때문입니다.

​

하지만 이것은 유일한 해답은 아닙니다. 사실 c=5 , n0=1 일때도 성립합니다. 왜냐하면 모든 n >= 1에 대해 5n^2 <= 5 * n^2이 성립하기 때문입니다. 또한 c=7 , n0=1 일때나 c=10 , n0=100 일때도 성립합니다.

​

즉, 빅오표기법의 증명은 여러 가지 방법으로 할 수 있으며, 한 가지 정답만 있는 것은 아닙니다. 중요한 것은 입력 크기가 충분히 커질 때 함수의 상한을 표현할 수 있는지 여부입니다.

​

요약하면, 빅오표기법은 알고리즘의 시간 복잡도나 공간 복잡도를 나타내는 방법으로, 입력 크기가 충분히 큰 경우에 실행 시간이나 메모리 사용량의 상한을 표현합니다. 빅오표기법의 증명은 어떤 상수 c와 n0가 존재해서 모든 n >= n0에 대해 f(n) <= c * g(n)이 성립한다는 것을 보여주는 것입니다. 문제에서 주어진 5n^2 <= O(n^2)을 증명하는 방법은 여러 가지가 있으며, 예제 풀이에서 제시된 방법 외에도 다른 방법들도 가능합니다.