Ich habe zu finden, ob die folgenden wahr oder falsch ist:Wenn f (n) ∈ ω (g (n)), dann 2^f (n) ∈ ω (2^g (n))
Wenn f (n) ω (g (n)), dann 2^f (n) ω (2^g (n))
Ich habe die Berechnungen f (n) = 1/n und g (n) = 1/n^2 und bekam das ans als falsch.
es sein sollte:
Wenn f (n) ∈ ω (g (n)), dann 2^f (n) ∈ Θ (2^g (n))
Könnte jemand Bitte überprüfen Sie dies?
Statement:f(n) ≥ g(n) ⋅ k für alle k ⇒ 2^f(n) ≥ 2^g(n)⋅k für alle k.
Ihr Gegenbeispiel ist korrekt: 1/n ≥ k/n² gilt für alle k. Wir können dies zeigen, indem sie die Grenze nehmen:
limn → ∞ (1/n)/(k/n²) = 1/k ⋅limn → ∞ n²/n = ∞
jedoch: 21/n ≥ 21/n²⋅ k falsch ist. Das können wir auch zeigen, indem sie die Grenze nehmen:
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
Die Aussage nur wahr gewesen wäre, wenn die Grenze unendlich ist.
Ein einzelnes Gegenbeispiel genügt, um zu beweisen, dass eine Aussage falsch ist, also sind Sie fertig.
Ich hoffte für einen Moment, das war APL – asawyer
Es scheint kontraintuitiv, dass, wenn f g dominiert, 2^f durch 2^g begrenzt ist (f könnte g um einen lächerlichen Betrag dominieren). Welche Berechnungen haben Sie durchgeführt, um den ursprünglichen Anspruch zu begründen? –
@Scott: Es ist kontraintuitiv, weil die Beispielfunktionen abnehmen. Normalerweise denkt man an wachsende Funktionen, wenn man von "Groß-O" - und "Klein-O" -Notationen spricht. –