Así que estoy leyendo un código de este sitio web: http://www.geeksforgeeks.org/write-ac-program-to-find-the-parity-of-an-unsigned-integer/
Y muestra cómo determinar si un número tiene paridad par o impar. Sin embargo, no entiendo por qué la eficiencia del tiempo de ejecución es log(n). Aquí está el código de referencia:
# include <stdio.h> # define bool int /* Function to get parity of number n. It returns 1 if n has odd parity, and returns 0 if n has even parity */ bool getParity(unsigned int n) { bool parity = 0; while (n) { parity = !parity; n = n & (n - 1); } return parity; }La eficiencia del tiempo de ejecución es O(log(n)), donde n es el valor del número entero que pasa. Sin embargo, esa es una forma poco convencional de usar la notación O.
Más frecuentemente, la notación O se expresa en términos del tamaño de la entrada en bits (el número de bits necesarios para representar la entrada), en cuyo caso el tamaño de la entrada es k=O(log2(n)) y el tiempo de ejecución es O(k).
(Aún más preciso, el tiempo de ejecución es Θ(s) donde s es el número de bits establecidos en n, aunque eso supone que las operaciones de bits son O(1)).
Vea esta pregunta So aquí
Como puede ver, no contamos los 1 usando esto, el bucle ejecutará exactamente el número de bits que son uno (1) (digamos p) en la representación binaria de n.
Por tanto, la complejidad es Θ(p).
y como el número máximo de bits utilizados para representar n es log2(n), por lo tanto, el límite asintótico superior id O(log2(n)).