Bits algorithme de comptage (Brian Kernighan) en un entier complexité temporelle
Quelqu'un peut-il explique pourquoi Brian Kernighan de l'algorithme prend O(log N) pour compter les bits (1s) en un entier. Une simple mise en œuvre de cet algorithme est ci-dessous (en JAVA)
int count_set_bits(int n){
int count = 0;
while(n != 0){
n &= (n-1);
count++;
}
return count;
}
Je comprends comment ça fonctionne en désactivant la plus à droite de bit, un par un, jusqu'à ce qu'il arrive à 0, mais je ne sais pas comment nous obtenons O(log N).
- n est représenté par log(n) bits. (En revanche, les k bits peut représenter les nombres aussi élevé que 2^k.) La vérification de chaque bit prend la constante de temps, de sorte que nous nous retrouvons avec log(n) fois.
- En Java, il devrait probablement être
while( n!=0 )
. Sinon, les nombres négatifs ne seront pas comptabilisés correctement. - Je vois..juste corrigé
- softwareengineering.stackexchange.com/questions/304876/...
- donc, si
N
est le nombre de bits, alors il estO(N)
, mais siN
estn
, alors il estO(log N)
Vous devez vous connecter pour publier un commentaire.
Cet algorithme passe par autant d'itérations que l', il y a des bits. Donc, si nous avons un mot de 32 bits uniquement avec le haut-bit est défini, il sera seulement aller une fois dans la boucle. Dans le pire des cas, il va passer une fois par bit. Un entier
n
alog(n)
bits, d'où le pire des cas estO(log(n))
. Voici votre code annoté à l'important bits (pun intended):O(log n)
. Brian Kernighan de l'algorithme seulement d'améliorer sur la moyenne des cas, ou dans le meilleur des cas: si nous supposons que la moitié des bits sont1
, alors la boucle est de la moitié le nombre de fois que peu à peu... si le nombre a juste 1 bit est défini, alors au lieu de 32 ou 64 fois (ou chaque fois que le bit est effacé et fairea
devenir0
, par exemple: boucle de 6 fois si c'est le 6ème bit set), puis Brian Kernighan de l'algorithme est juste une fois dans la boucle. Si seulement 2 bits sont1
, puis Brian Kernighan de l'algorithme de la boucle par deux fois seulement.theta(log n)
alors que Kernighans estO(log n)
.Il y a étage(lg(N)) + 1 bits significatifs dans N -- c'est un logarithme en base 2. Le nombre de bits à 1 dans n est plus ce. De sorte que le temps aura asymptotique à la limite supérieure de O(lg(N)) = O(log(N)).
Cette question est vraiment sur le sens de N en notation grand O, pas de la complexité de l'algorithme.
N désigne la taille des données. Mais dans le cas où les où les "données" est un numéro unique, vous devez définir ce que vous comprenez que la taille des données. La valeur d'un nombre ou la longueur de sa représentation.
De l'OMI, l'algorithme est O(N). Parce que dans ce problème de comptage de 1 dans la représentation binaire de l'OMI pertinentes de la taille des données est la longueur de la nombre de à la représentation, c'est la valeur c'est à dire la longueur du flux de bits. Et évidente pire des cas, tous les 1 la prise de N itérations.
Mais si vous considérez la valeur de N que la taille des données, c'est la représentation log(N) la longueur de sorte que vous pouvez dire que c'est O(log(N))
PS Aussi big O la notation n'a de sens que si vous l'appliquez l'algorithme pour arbitrairement élevée en nouvelle-écosse. Dans ce code N est limitée par int taille, de sorte que vous pouvez dire que c'est O(1) car il sera à plus de 64 itérations de boucle (pour la version 64 bits ints)