notacion - complejidad de algoritmos pdf

Mientras que la complejidad del tiempo del ciclo O(logn)

Question

No puedo entender por qué la complejidad de tiempo para este código es O (logn) :

double n;
/* ... */
while (n>1) {
     n*=0.999;
}

Al menos eso dice en mis materiales de estudio.

Answer 1

Desea calcular cuántas iteraciones necesita antes de que n sea ​​igual a (o menor que) 1.

Si llama al número de iteraciones para k desea resolver

n * 0.999 ^ k = 1

Dice así

n * 0.999 ^ k = 1

0.999 ^ k = 1 / n

log (0.999 ^ k) = log (1 / n)

k * log (0.999) = -log (n)

k = -log (n) / log (0.999)

k = (-1 / log (0.999)) * log (n)

Para big-O, solo nos importa "el panorama general", así que desechamos las constantes. Aquí log(0.999) es una constante negativa, por lo que (-1 / log (0.999)) es una constante positiva que podemos "tirar", es decir, establecer en 1. Entonces obtenemos:

k ~ log (n)

Entonces el código es O (logn)

A partir de esto, también puede observar que el valor de la constante (es decir, 0,999 en su ejemplo) no tiene importancia para el cálculo del gran O. Todos los valores constantes mayores que 0 y menores que 1 darán como resultado O (logn).

Answer 2

El logaritmo tiene dos entradas: una base y un número. El resultado de un logaritmo es la potencia que necesita para elevar la base para alcanzar el número dado. Dado que su base es 0.999, el número es el primero más pequeño que 1 y tiene un escalar, que es n, de hecho, el número de pasos depende de la potencia que necesita para elevar su base para lograr un número tan pequeño, que se multiplicó por n rendirá un número más pequeño que 1. Esto corresponde a la definición del logaritmo, con el cual comencé mi respuesta.

EDITAR:

Piénselo de esta manera: tiene n como entrada y busca la primera k donde

n * .999 ^ k <1

ya que estás buscando k incrementándolo, ya que si tienes l> = n en un paso, entonces tendrás l * .999 en el siguiente paso. Al repetir esto, se logra una complejidad logarítmica para su algoritmo de multiplicación.

Answer 3

Imagina si el código fuera el siguiente:

double n;
/* ... */
while (n>1) {
     n*=0.5;
}

Debería ser intuitivo ver cómo esto es O (logn), espero.

Cuando multiplicas por 0.999 en cambio, se vuelve más lento por un factor constante, pero por supuesto la complejidad todavía se escribe como O (logn)