Réduction de la complexité temporelle

int main() 
{ 
    int n ; 
    std::cin >> n; // or scanf ("%d", &n); 
    int temp; 
    if(n ==1) temp = 1; // if n is 1 number is power of 2 so temp = 1 
    if(n % 2 != 0 && n!= 1) temp =0; // if n is odd it can't be power of two 
    else 
    { 
     for (;n && n%2 == 0; n /= 2); 
     if(n > 0 && n!= 1) temp = 0; // if the loop breaks out because of the second condition 
     else temp = 1; 
    } 

    std::cout << temp; // or printf ("%d", temp); 
}

Le code ci-dessus vérifie si un nombre est une puissance de deux. La complexité de l'exécution la plus défavorable est O (n). Comment optimiser le code en réduisant la complexité temporelle?Réduction de la complexité temporelle

Source

2011-01-25 AlgorithmGeek

La complexité d'exécution de votre code au pire est O (log n), vous pouvez encore faire mieux (O (1)) comme le montre ci-dessous – CashCow

Essayez if(n && (n & (n-1)) == 0) temp = 1; pour vérifier si un nombre est une puissance de deux ou non.

Par exemple:

n = 16;

1 0 0 0 0 (n) 
& 0 1 1 1 1 (n - 1) 
    _________ 
    0 0 0 0 0 (yes)

un nombre qui est la puissance de 2 ne comporte qu'un seul bit.

n & (n - 1)unsets the rightmost set bit.

Durée O(1) ;-)

Comme @GMan remarqué n doit être un entier non signé. L'opération au niveau du bit sur les entiers signés négatifs est définie par l'implémentation.

Source

2011-01-25 09:57:30

Joli petit diagramme. Bien sûr, «n» doit être «non signé» pour garantir que cela fonctionne. – GManNickG

@GMan: Oh oui! Permettez-moi d'ajouter cela à mon poste .. –

si ce n'est pas le cas, changer le «n» en «n> 0» fait le travail. – etarion

Que pensez-vous de cela?

bool IsPowerOfTwo(int value) 
{ 
    return (value && ((value & (value-1)) == 0); 
}

Source

2011-01-25 09:58:21 EboMike

essayez ceci: bool isPowerOfTwo = n && !(n & (n - 1));

Source

2011-01-25 09:59:36 Botz3000

Au lieu de diviser un nombre par 2, vous pouvez passer à droite par 1. Ceci est une règle d'optimisation universelle pour la division par 2,4,8,16,32 et bientôt. Cette division peut être remplacée par le décalage droit 1,2,3,4,5 et ainsi de suite. Ils sont mathématiquement équivalents.

Le décalage est meilleur, car l'instruction de division de l'assembleur est terriblement inefficace sur la plupart des architectures CPU. Une instruction de décalage logique est exécutée beaucoup plus rapidement.

Toutefois,, le compilateur devrait être en mesure de faire cette optimisation pour vous, ou il a un mauvais optimiseur. Du point de vue du style, il peut être préférable d'écrire des opérateurs de division et de modulo dans le code C, mais vérifiez que le compilateur les optimise réellement pour les opérations de décalage.

Source

2011-01-25 11:05:13 Lundin

bool ifpower(int n) 
{ 
    if(log2(n)==ceil(log2(n))) return true; 
    else return false; 
}

Source

2014-10-16 06:29:35 rajeev

Réduction de la complexité temporelle

Répondre

Questions connexes