다음 질문을 이해하는 데 문제가 있습니다. 그것은 밝힌다 :큰 -O 표기법의 지수 증가
다른 기하학 가치 를위한 지수 함수가 다른 성장 순서가다는 것을 증명하십시오.
예를 들어 나에게 보이는 것처럼, n을 고려해보십시오. a = 3 인 경우 a = 2 일 때보 다 성장률이 커집니다. 그것은 분명히 보인다. 그것은 정말로 질문이 원하는 것입니까? 어떻게해야할까요?
미리 도움을 주셔서 감사합니다.
f (n) ∈ O (g (n))는 모든 n ≥ k에 대해 0 ≤ f (n) ≤ cg (n)가되도록 양수 상수 c와 k가 있음을 의미합니다. c와 k의 값은 함수 f에 대해 고정되어야하며 n에 의존해서는 안됩니다.
보편성을 잃지 않고 1> a> b라고하고 b^n ∈ O (a^n)라고 가정하십시오. 이것은 모든 n ≥ k에 대해 0 ≤ b^n ≤ ca^n 인 양의 상수 c와 k가 존재 함을 의미하며, 이는 불가능합니다.
b n n ≤ ca n)^n ≤ c for all n ≥ k
이는 b/a> 1이기 때문에 lim (b/a)^n = + inf와 모순이된다.
경우 1> A> B 다음 B^N ∉ O (a^N)지만^N ∈ O (b^n)이 너무 O (a^N) ⊊O (b^N)
정식 증명 절차에 익숙합니까? 그렇다면 도움이 될 수있는 몇 가지 기존 정리가 있어야합니다. 또한 그래프를 플로팅하는 것은 증명이 아니라 **이 조회의 단일 인스턴스를 시각적으로 나타냅니다. –
'A'와'B'는'A> B' 조건을 만족하는 양의 실수입니다. 이것은 양의 실수 'C'를 취하고 양측에 곱하기 때문에 'A * C> B * C'입니다. 이것은 모든 'C'에 해당되며'C = A'와'A * A> B * A' 만 만듭니다. 'A> B' 이후로, 이것은'A^2> B^2'와 다른 성장률을 필요로합니다. 이것은 완전한 증거가 아닙니다. 나는 그것을 실제로 살리기 위해 더 많은 시간을 소비해야 할 것입니다. –