Calculer la valeur de x ^ y en O(log n)

Question d'entrevue:

Calculer x ^ y en O(log n)

Il y a différentes réponses comme "l'Utilisation de l'Indien de la Puissance de l'algorithme" ou

double power(double x, int y) 
{
    if(y == 0) return 1;

    double d = power(x, y/2);

    if(y%2 == 0) return d*d;
    else return x*d*d;
}
  1. est-il une bonne réponse?
  2. est-il une meilleure façon d'écrire un code pour cette question?
Est-ce devoirs?
non, c'est une question d'entrevue, vous pouvez voir le tag 😉
le reste est redondant

OriginalL'auteur Elnaz | 2012-04-17

  1. 8

    Ce qui est appelé L'Exponentiation par la Quadrature. Aussi loin que la mise en œuvre va, c'est une question de goût. Votre récursive de la mise en œuvre est bonne, mais non récursive implémentations (à partir du lien ci-dessus) peut paraître un peu plus propre pour les gens qui n'aiment pas la récursivité ou de croire, à tort, qu'il est en quelque sorte le "gaspillage" ou "lent".

    OriginalL'auteur dasblinkenlight

  2. 2

    Des Questions sur les opérations mathématiques de base, et des questions sur la complexité de calcul, sont généralement traitées rapidement par Wikipedia.

    L'Exponentiation: Calcul efficace de l'ensemble des pouvoirs

    En général, le nombre de multiplication d'opérations nécessaires pour calculer bn peut être réduite à Θ(log n) en utilisant l'exponentiation par la quadrature ou (plus généralement) ajout de la chaîne d'exponentiation. Trouver la séquence minimale de multiplications (le minimum de longueur de plus de la chaîne de l'exposant) est un problème difficile pour qui n'algorithmes efficaces sont actuellement connus (voir sous-ensemble somme problème), mais beaucoup raisonnablement efficace des algorithmes heuristiques sont disponibles.

    OriginalL'auteur Potatoswatter

  3. 1

    Nous allons analyser:

    power est appelée (par l'intermédiaire de la récursivité) autant de fois que l'original y est divisible par 2 (c'est le plus grand nombre, k, tels que 2^k < y). Cela signifie que le nombre de calculs est à peu près k=log_2(2^k)=log_2(y)~=log(y), donc c'est une bonne réponse.

    La réponse à la "meilleure façon" dépend de ce qui est considéré comme "meilleur"

    OriginalL'auteur Attila

  4. 1

    Voici la façon de le faire:

    disons que vous voulez à 2^1024, ... wait for it ... 11 multiplications

    vous le faire de cette façon

    2*2 = 2^2
2^2 * 2^2 = 2^4
2^4 * 2^4 = 2^8
2^8 * 2^8 = 2^16
....
2^512 * 2^512 = 2^1024

    donc, fondamentalement, il vous suffit d'écrire votre exposant en base 2 et d'obtenir toutes les multiplications

    OriginalL'auteur scibuff

  5. -2

    Ici est beaucoup plus rapide: % est une opération très coûteuse, pour la remplacer par une opération au niveau du bit est une des économies considérables; aussi remplacer y/2 avec y>>1:

    double power(double x, int y) {
    if(y == 0) return 1;

    double d = power(x, y>>1);

    if((y&1) == 0) return d*d;
    else return x*d*d;
}
    -1. Avez-vous vérifier l'amélioration de la performance par le profilage? x%2 est universellement optimisé pour x&1, et de la même façon avec x/2 et x>>1. Microoptimizations ne sont pas une bonne idée, sauf si vous êtes à la résolution d'un problème découvert en lisant le démontage. Tout cela permet d'accomplir est d'utiliser le mauvais opérateurs pour le travail, rendant les règles de priorité encore plus tordu. Par exemple, (y&1 == 0) ne fait pas ce que vous pensez que cela fonctionne.
    Alors que je suis totalement d'accord avec @Potatoswatter, je voudrais ajouter que if(y&1) est également possible (malgré le mauvais dans certains styles de code) 😀
    D'autre part, dans certains contextes, l'écriture >> 1 est plus évident que / 2 et a même distincte de la sémantique, par exemple en PHP où / flotter division et >> 1 jette les opérandes entiers.

    OriginalL'auteur kasavbere