Warum ist

$3^n = 2^{O(n)}$ ist anscheinend wahr. Ich dachte, dass es falsch ist, weil schneller wächst als jede Exponentialfunktion mit einer Basis von 2.$3^n$

Wie ist wahr?$3^n = 2^{O(n)}$

Mit etwas Algebra (und Ändern der Konstante in ) können wir tatsächlich die Basen ändern.$O(n)$

$$3^n = (2^{\log_2 3})^n = 2^{n\log_2 3}$$

Da eine Konstante ist, ist n log 2 3 = O ( n ) . Also 3 n = 2 O ( n ) .$\log_2 3$$n\log_2 3 = O(n)$$3^n = 2^{O(n)}$

Ich bin mir nicht sicher, was Sie unter " wächst schneller als jede Exponentialfunktion mit einer Basis von 2" verstehen. 2 n = o ( 3 n ) natürlich, aber es scheint, dass Sie etwas allgemeineres meinen. Ich vermute, dass Ihre Aussage für etwas wie O ( 3 n ) gilt , bei dem Sie die Basis mit einer Konstanten multiplizieren, im Gegensatz zu 2 O ( n ), bei dem Sie die Zahl im Exponenten mit einer Konstanten multiplizieren.$3^n$$2^n = o(3^n)$$O(3^n)$$2^{O(n)}$

wächst schneller als jede Exponentialfunktion mit einer Basis von 2 .$3^n$$2$

Wahr. Dies impliziert, dass nicht wahr sein kann. Aber was Sie hier haben, ist 2 O ( n ) .$3^n = O(2^n)$$2^{O(n)}$

Denken Sie daran, dass wirklich eine Menge von Funktionen ist, und genau genommen sollten wir 3 n ∈ 2 O ( n ) (oder sogar ( n ↦ 3 n ) ∈ 2 O ( n ↦ n ) ) schreiben . Die rechte Seite ist nicht das Exponential einer Funktion, sondern das Exponential einer Reihe von Funktionen. Erweiterung der Definition von big oh:$O(f(n))$$3^n \in 2^{O(n)}$$(n \mapsto 3^n) \in 2^{O(n \mapsto n)}$

$$2^{O(n)} = 2^{\{f \;\mid\; \exists N, \exists p, \forall n \ge N, f(n) \le p n\}} = \{(n \mapsto 2^{f(n)}) \mid \exists N, \exists p, \forall n \ge N, f(n) \le p n\}$$

Da die Exponentialfunktion zunimmt, können wir die Ungleichung aus dem Exponential herausheben :$n \mapsto 2^n$

$$2^{O(n)} = \{g \mid \exists N, \exists p, \forall n \ge N, g(n) \le 2^{p \, n}\}$$

Contrast mit

$$O(2^n) = \{g \mid \exists N, \exists k, \forall n \ge N, g(n) \le k \, 2^{n}\}$$

$2^{O(n)}$$O(2^n)$$2^{p \, n} = 2^p 2^n$$n \ge 0$$3^n \le 2^{\log_2 3} 2^n$$N = 0$$p = \log_2 3$$3^n \in 2^{O(n)}$

$3^n=2^{O(n)}$$O(n)$

$3^n < 2^{kn}$$\log_2$

$n\log_2(3^n) < kn\log_2(2)$

$k > \log_2(3)$

$2^{kn}$$3^n \iff k > \log_2(3)$