Est-ce que le décalage de bits est en O(1) ou en O(n) ?

Question

Les opérations de décalage sont-elles de complexité O(1) ou O(n) ?

A-t-il du sens que les ordinateurs nécessitent généralement plus d'opérations pour décaler de 31 places au lieu d'une place?

Ou a-t-il du sens que le nombre d'opérations requis pour le décalage est constant quel que soit le nombre de places que nous devons décaler?

PS : se demander si hardware est une balise appropriée..

Answer 1

Pour le matériel normal, les registres de taille fixe sont constants, peu importe le nombre d'emplacements que vous décalez.

Notez également que l'utilisation de la notation O est assez étrange ici, vous l'utiliseriez normalement pour indiquer la complexité algorithmique basée sur le nombre de décalages, et non sur le nombre d'emplacements à décaler.

Answer 2

Par exemple, selon le Tableau C-17. Instructions d'usage général du Manuel de référence sur l'optimisation des architectures Intel® 64 et IA-32 :

SAL/SAR/SHL/SHR reg, imm   Latence de 1 cycle
SAL/SAR/SHL/SHR reg, cl    Latence de 1.5 cycles

Il s'agit donc toujours d'un facteur constant et O(1.5) = O(1). Il peut y avoir des microarchitectures plus simples en dehors de la norme, mais en général, O(1).

Answer 3

Toute implémentation, même si elle nécessite n opérations, sera considérée comme O(1).

Vous avez le nombre de bits plafonné, donc il y a un nombre maximal de bits qui peuvent être décalés.

Même s'il faut plus d'opérations pour les décalages de bits, une seule opération prendra un temps X. Le maximum sera MAX_BITS*X.

Ainsi, le temps maximum d'opération est constant.

La notation O devrait expliquer comment le temps croît avec la taille de la tâche.

Exemple: Vous effectuez des décalages de bits aléatoires dans une boucle.

Si vous l'exécutez 1000 ou 100000 fois, le temps dont vous aurez besoin sera strictement O(n), où n est le nombre d'itérations. Si le décalage de bit était considéré comme O(n), le temps de la boucle aurait dû être O(n^n), ce qui n'est pas le cas.