Deje y = 2 ^ x
Tomando logaritmo natural en ambos lados
log y = x log 2.
Como log 2 es 0.301, que es aproximadamente 0.3
- ¿Cuáles son algunos métodos que se pueden usar para probar límites inferiores para los tiempos de ejecución de los algoritmos?
- ¿Cuál es el significado del lema de aislamiento?
- ¿Ha habido alguna investigación relacionada con la coinducción y el patrón de observación?
- ¿Un bucle siempre tiene un punto de partida?
- ¿Las personas descubren o inventan algoritmos? ¿Cómo?
log y = 0.3 * x.
La parte entera del resultado 0.3 * x es la parte característica del logaritmo y es un indicador de rango del valor de y, que puede usarse para estimar el tamaño de y.
Tratemos de calcular un ejemplo simple de 2 ^ 10.
característica = 10 * 0.3 = 3, lo que significa que el valor de 2 ^ 10 es mayor que igual a 10 ^ 3, o el valor de 2 ^ 10 tiene que ser mayor que 1 seguido de 3 ceros y definitivamente menor de 1 seguido de 4 dígitos
Como es evidente, 2 ^ 10 = 1024 y, de hecho, es mayor que nuestra estimación.
Estimación del dígito más significativo para una mejor precisión.
Si observamos el dígito más significativo de potencias de 2, entonces observamos una serie repetitiva de frecuencia 10 como se muestra
1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072
Ahora solo los dígitos más significativos de los poderes
1 2 4 8 1 3 6 1 2 5 y los patrones
1 2 4 8 1 3 6 1 2 5 y así el patrón se repite.
Tratemos de estimar 2 ^ 32 que es 4294967296.
Estima el tamaño del número: 32 * 0.3 = 9.6, lo que significa que es mayor que 1 seguido de 9 dígitos.
Estime el dígito más significativo: 32% 10 (recordatorio cuando 32 se divide por 10) = 2. A partir de 0, el valor en el índice 2 en la secuencia de repetición es 4 (0th pos = 1, 1st pos = 2, 2nd pos = 4, 3rd pos = 4). Tenemos que hacer el recuento comenzando desde cero porque la operación de recordatorio cuando se realiza con 10 siempre da un valor entre 0 y 9.
La respuesta final es el dígito más significativo 4 y 9 ceros después. El valor estimado 4000000000 está cerca del valor real 4294967296.
Para resumir
Para 2 ^ x, 0.3 * x será el número de ceros después del dígito más significativo.
(x% 10) el número de la serie recurrente con índice que comienza en 0, será el dígito más significativo.
Como complemento, x% 10 no es más que el dígito de las unidades de x.
Espero que esto ayude.
