Dev Faq
12
votes

Est 2 ^ (2n) = O (2 ^ n)

xxx pré>

Je crois que celui-ci est correct car n + 1 ~ = n code>. p>

p> 

Is 2(2n) = O(2n)?

0 commentaires

7 Réponses :

6
votes

Notez que 

22n = (2n)2

3 commentaires

Alors, quel est le big-o pour 2 ^ 2n?

@Dylanczenski 2 ^ 2n = (2 ^ 2) ^ n = o (4 ^ n)

Quels sont les noms actuels de ces deux?

3
votes

Pour répondre à ces questions, vous devez faire attention à la définition de la notation Big-O. Vous devez donc demander:

y a-t-il une constante C telle que 2 ^ (n + 1) <= c (2 ^ n) (à condition que n soit assez grand)?

et la même chose vaut pour l'autre exemple: y a-t-il une constante C telle que 2 ^ (2n) <= C (2 ^ n) pour tout N qui est assez grand?

Travailler sur ces inégalités et vous serez sur le chemin de la solution.

0 commentaires
7
votes

Je suppose que vous venez de quitter la notation O () sur le côté gauche.

o (2 ^ (n + 1)) est identique à O (2 * 2 ^ N) et vous pouvez toujours retirer des facteurs constants, de sorte qu'il est identique à O (2 ^ N).

Cependant, des facteurs constants sont la seule chose que vous puissiez sortir. 2 ^ (2n) peut être exprimé comme (2 ^ n) (2 ^ n) et 2 ^ N n'est pas une constante. Donc, la réponse à vos questions est oui et non.

1 commentaires

2 ^ (n + 1) = O (2 ^ n) est courant, une notation incroyablement malheureuse pour dire "L'ordre de 2 ^ (n + 1) est BIG-O (2 ^ n) " si j'avais mon chemin, au lieu de cette terrible o, Ω, θ notation, nous utiliserions un symbole θ en conjonction avec ≤, ≥ et = pour spécifier la commande; La déclaration ci-dessus serait alors écrite comme θ (2 ^ (n + 1)) ≤ θ (2 ^ n) . Malheureusement, ce n'est tout simplement pas la façon dont cela fonctionne :(

23
votes

Le premier cas est évidemment vrai - vous venez de multiplier la constante C en 2.

Réponses actuelles à la deuxième partie de la question, ressemblez à un handwaving pour moi, alors je vais essayer de donner une explication de mathématiques appropriée. Supposons que la deuxième partie est vraie, puis de la définition de Big-o , vous avez:

Entrez la description de l'image ici

Ce qui est clairement faux, car il n'y a pas de telle constante qui satisfait à une telle inégalité.

0 commentaires
8
votes

Revendication: 2 ^ (2n)! = O (2 ^ n)

Proof par contradiction:

  1. supposons: 2 ^ (2n) = O (2 ^ n)
  2. Ce qui signifie qu'il existe C> 0 et n_0 s.t. 2 ^ (2n) <= C * 2 ^ N pour tous N> = N_0
  3. Division des deux côtés par 2 ^ N, nous obtenons: 2 ^ n <= C * 1
  4. contradiction! 2 ^ N n'est pas limité par une constante c.

    donc 2 ^ (2n)! = O (2 ^ n)

0 commentaires
4
votes

2 n + 1 = O (2 n ) parce que 2 n + 1 = 2 = 2 = 2 = 2 = 2 = 2 = 2 = 2 = 2 = 2 = 2 = 2 > 1 * 2 n = O (2 n ). Supposons 2 2n = O (2 n ), il existe une constante C telle que pour N au-delà de certains n 0 , 2 22 <= C 2 n . Diviser les deux côtés par 2 n , nous obtenons 2 n 0 qui peut rendre cela vrai, l'hypothèse est donc fausse et 2 2n ! = O (2 n )

0 commentaires
-1
votes

Nous allons utiliser => A ^ (m * n) = (a ^ m) ^ n = (a ^ n) ^ m Maintenant,

2 ^ (2 * N) = (2 ^ n) ^ 2 = (2 ^ 2) ^ n

donc,

(2 ^ 2) ^ n = (4) ^ n

Par conséquent,

o (4 ^ n)

évidemment,

taux de croissance de (2 ^ n) <(4 ^ n)

0 commentaires

Articles qui pourrait vous intéresser :

Comment arrondir, sol, plafond, tronquer
Points dans le cercle - performance
Math.pow () dans Java 8 et Java 13 renvoie un résultat différent
THREE.js Raycasting très lent contre un seul objet poly (faces)> 500k, intersection de ligne avec globe