I는 다음이 참인지 거짓인지를 찾을 수있다 :경우 F (N) ∈ ω (N g()) 다음, 2^F (N) ∈ ω (n은 2^g())
f (n) = 1/n과 g (n) ∈ ω (2^g (n)) 일 때, n) = 1/n^2이고 ans는 거짓으로 나타납니다.
이 같아야
경우 F (N) ∈ ω (N g()) (n은 2^g()) (N), 다음 2^F ∈ Θ
수 어떤 사람 이것을 확인해 주시겠습니까?
진술 : 모든 k에 대한f(n) ≥ g(n) ⋅ k 모든 k에 대한 2^f(n) ≥ 2^g(n)⋅k을 ⇒.
반례 사례가 맞습니다 : 1/n ≥ k/n²은 모두 k에 해당합니다. 우리는 한계를 고려하여이를 표시 할 수 있습니다 : 그러나
limn → ∞ (1/n)/(k/n²) = 1/k ⋅limn → ∞ n²/n = ∞
: 21/n ≥ 21/n²⋅ k은 false입니다. 우리는 또한 한계를 고려하여이를 표시 할 수 있습니다 :
limn → ∞ 21/n/(21/n² ⋅ k) = = 1/k lim of 21/n - 1/n² = = 1/k lim of 2(n - 1)/n² = 1/k ⋅ 2⁰ = = 1/k
성명은 사실이었을 것이다 한도가 무한대 인 경우.
단일 반례는 진술이 거짓임을 입증하기에 충분하므로 완료되었습니다.
나는 잠시 동안 이것이 APL – asawyer
이었으면 좋겠다. f가 f를 지배하면 2^f가 2^g (f가 우스운 양으로 g를 지배 할 수있다)로 묶여 있다는 것이 반 직관적 인 것처럼 보인다. 처음 청구를하기 위해 당신이 계산 한 것은 무엇입니까? –
@Scott : 예제 함수가 줄어들 기 때문에 반 직관적입니다. 하나는 대개 빅 오 (Big-O)와 리틀 오 (Little-O) 표기법에 대해 말할 때 기능이 증가한다고 생각합니다. –