Pourquoi est-ce

$3^n = 2^{O(n)}$est apparemment vrai. Je pensais que c'était faux car$3^n$ croît plus rapidement que n'importe quelle fonction exponentielle avec une base de 2.

Comment est $3^n = 2^{O(n)}$ vrai?

Avec une algèbre (et changer la constante dans le $O(n)$), nous pouvons en fait changer les bases.

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

Depuis $\log_2 3$ est une constante, $n\log_2 3 = O(n)$. Donc$3^n = 2^{O(n)}$.

Je ne sais pas ce que tu veux dire par "$3^n$ croît plus rapidement que n'importe quelle fonction exponentielle avec une base de 2. " $2^n = o(3^n)$bien sûr, mais il semble que vous vouliez dire quelque chose de plus général. Je suppose que votre déclaration s'applique à quelque chose comme$O(3^n)$, où vous multipliez la base par une constante, par opposition à $2^{O(n)}$ où vous multipliez le nombre de l'exposant par une constante.

$3^n$ croît plus rapidement que toute fonction exponentielle avec une base de $2$.

Vrai. Cela implique que$3^n = O(2^n)$Ne peut pas être vrai. Mais ce que vous avez ici, c'est$2^{O(n)}$.

Rappeler que $O(f(n))$ est vraiment un ensemble de fonctions, et à proprement parler, nous devrions écrire $3^n \in 2^{O(n)}$ (ou même $(n \mapsto 3^n) \in 2^{O(n \mapsto n)}$). Le côté droit n'est pas l'exponentielle d'une fonction, mais l'exponentielle d'un ensemble de fonctions. Élargir la définition du grand 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\}$$

Depuis la fonction exponentielle $n \mapsto 2^n$ augmente, on peut sortir l'inégalité de l'exponentielle:

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

Contraste avec

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

Dans $2^{O(n)}$, la constante multiplicative est à l'intérieur de l'exponentielle. Dans$O(2^n)$, il est multiplié par l'exponentielle. $2^{p \, n} = 2^p 2^n$, nous avons donc (pour tout $n \ge 0$) $3^n \le 2^{\log_2 3} 2^n$c'est-à-dire que nous pouvons prendre $N = 0$ et $p = \log_2 3$, montrant que $3^n \in 2^{O(n)}$.

$3^n=2^{O(n)}$ est en fait vrai parce que si vous vous souvenez $O(n)$définition, vous verrez que vous pouvez ajouter / multiplier par n'importe quelle constante. Donc:

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

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

$k > \log_2(3)$

Comme vous pouvez le voir $2^{kn}$ est plus grand alors $3^n \iff k > \log_2(3)$