Kenapa

$3^n = 2^{O(n)}$rupanya benar. Saya pikir itu salah karena$3^n$ tumbuh lebih cepat daripada fungsi eksponensial apa pun dengan basis 2.

Bagaimana $3^n = 2^{O(n)}$ benar?

Dengan beberapa aljabar (dan mengubah konstanta di $O(n)$), kita benar-benar dapat mengubah basis.

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

Sejak $\log_2 3$ adalah konstanta, $n\log_2 3 = O(n)$. Begitu$3^n = 2^{O(n)}$.

Saya tidak yakin apa yang Anda maksud dengan "$3^n$ tumbuh lebih cepat daripada fungsi eksponensial apa pun dengan basis 2. " $2^n = o(3^n)$tentu saja tetapi sepertinya Anda bermaksud sesuatu yang lebih umum. Dugaan saya adalah bahwa pernyataan Anda berlaku untuk sesuatu seperti$O(3^n)$, di mana Anda mengalikan basis dengan konstanta, berlawanan dengan $2^{O(n)}$ di mana Anda mengalikan angka dalam eksponen dengan konstanta.

$3^n$ tumbuh lebih cepat daripada fungsi eksponensial apa pun dengan basis $2$.

Benar. Ini menyiratkan bahwa$3^n = O(2^n)$tidak mungkin benar. Tetapi apa yang Anda miliki di sini adalah$2^{O(n)}$.

Ingat itu $O(f(n))$ benar-benar seperangkat fungsi, dan sebenarnya kita harus menulis $3^n \in 2^{O(n)}$ (atau bahkan $(n \mapsto 3^n) \in 2^{O(n \mapsto n)}$). Sisi kanan bukanlah eksponensial dari suatu fungsi, tetapi eksponensial dari serangkaian fungsi. Memperluas definisi big oh:

$$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\}$$

Karena fungsi eksponensial $n \mapsto 2^n$ meningkat, kita dapat mengangkat ketidaksetaraan dari eksponensial:

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

Kontras dengan

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

In $2^{O(n)}$, the multiplicative constant is inside the exponential. In $O(2^n)$, it is multiplied by the exponential. $2^{p \, n} = 2^p 2^n$, so we have (for any $n \ge 0$) $3^n \le 2^{\log_2 3} 2^n$, i.e. we can take $N = 0$ and $p = \log_2 3$, showing that $3^n \in 2^{O(n)}$.

$3^n=2^{O(n)}$ is in fact true because if you recall $O(n)$ definition you will see that you can add/multiply by any constant. So:

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

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

$k > \log_2(3)$

So as you can see $2^{kn}$ is bigger then $3^n \iff k > \log_2(3)$