양수가있는 Big-O

Question

이 Big-O/Computational Complexity 문제 에서 a와 b는 1보다 큰 양의 상수이고 n은 가변 매개 변수입니다.

는 I 가정한다는 ^{N + 1} = O (a ^N)와, ^BN = O (a ^N) & ^{N + B} = O (a ^N)

먼저 내가 이것을 가정 할 때 올바른지 알아야합니다.

그렇다면 어떻게 f (n) = O (f (n))인지 증명할 수 있습니다.

Answer 1

회수가 큰 O의 정의 :

F (N) ∈ O (g (N)의) 포지티브 상수 C와 K가있는 수단이되도록 0 ≤ F (N) ≤ CG (n) 모든 n ≥ k에 대해. c와 k의 값은 함수 f에 대해 고정되어야하며 n에 의존해서는 안됩니다. ^{N + 1}

하자 g = F, C = 1, K = 0, 다음 F의 사소한 데모가 (N) ∈ O (N F()) 마찬가지로

, = a⋅a ^N,하자 F가 (n)은 ^{N + 1}, g (n)을 O의 ^N, C = A, K = 0, 다시 증명 = (a ^{N + 1}) = O (a ⁿ)는 사소하다. O (a ^{n + b}) = O (a ⁿ)의 증명은 동일합니다.
O A의 (a ^N) O와 동일하지 않은 (^BN은)는, B는> 1 참조 Exponential growth in big-o notation