O (O (f)))는 무엇을 의미합니까?

Question

빅 오 표기법에 대한 이해가 있습니다. 그러나 O (O (f (n)))가 의미하는 것을 어떻게 해석 할 수 있습니까? 성장률의 증가율을 의미합니까? 보기의 빅 - 오 관점에서

Answer 1

x = O(n) 기본적으로 일부 상수는 k 인 경우 x <= kn을 의미합니다.

따라서 x = O((O(n)) 일부 상수 q위한 수단 x <= pqn 어떤 일정한 p위한 수단 x <= pO(n).

Let k = pq.

다음으로 x = O((O(n)) = O(n).

즉, O(O(f(n))) = O(f(n))입니다.

궁금한 점은 어디에서 그런 표기법을 사용 했습니까?

Answer 2

:

g(n) = O(f(n))는 일부 K에 대한 g(n) <= K*f(n)을 의미 일부 n > n1, n2 후 약간의 L, M에 대한 h(n) <= L * M * f(n) 같은

그러나 h(n) = O(O(f(n))는 의미 일 (일부 N1 후) .