problema de explicación de tiempo de ejecución único para bucle

8

Estoy analizando algunos tiempos de ejecución de diferentes bucles for, y a medida que obtengo más conocimiento, tengo curiosidad por comprender este problema que todavía tengo que descubrir. Tengo este ejercicio llamado "Cuántas estrellas están impresas":

for (int i = N; i > 1; i = i/2) System.out.println("*");

Las respuestas para elegir es A: ~log N B: ~N C: ~N log N D: ~0.5N^2

Entonces la respuesta debería ser A y estoy de acuerdo con eso, pero por otro lado ... Digamos N = 500qué sería Log Nentonces. Sería 2.7. Entonces, ¿qué pasa si decimos eso N=500en nuestro ejercicio anterior? ¿Eso definitivamente imprimiría más estrellas han 2.7? ¿Cómo se relaciona eso?

Porque tiene sentido decir que si el ciclo for tuviera este aspecto:

for (int i = 0; i < N; i++)

imprimiría Nestrellas.

Espero encontrar una explicación para esto aquí, tal vez estoy interpretando mal todas estas cosas y pensando mal. Gracias por adelantado.

algorithms complexity big-o runtime owwyess
fuente
¿Cómo es esto diferente de su pregunta anterior? Tiempo de ejecución asintótico de bucles for
mosquito
Esto no tiene nada que ver con los tiempos de ejecución asintóticos.
owwyess
1
Esa opción solo tiene sentido si se entiende el logaritmo de base 2, no el logaritmo de base 10.
Kilian Foth
3
¿Qué base estás asumiendo para obtener Log 500 = 2.7? ¿y esa base aparece en algún lugar de su código? Nota: solo eres un factor constante diferente con registros de diferentes bases
Caleth
2
@Caleth el logaritmo de base no aparecen en el código: i = i/2la base es dos, porque el bucle está revirtiendo multiplicación repetida por dos.

Respuestas:

34

Has pasado por alto la característica clave de la base de logaritmo .

Como ise divide entre 2 en cada iteración, el tiempo de ejecución es logarítmico con la base 2. Y

log 2 (500) ~ 8.9

Lo que estás viendo es

log 10 (500) ~ 2.7

(logaritmo con base 10)

Por cierto, la razón por la cual la base a menudo se omite en las discusiones en tiempo de ejecución (y su calculadora probablemente no tiene un botón para el registro 2 ) es que debido a los mecanismos de las matemáticas logarítmicas, una base diferente corresponde a un factor constante y, por lo tanto, no es relevante cuando ignoras factores constantes de todos modos. Se puede calcular fácilmente:

log a (x) = log b (x) / log b (a)

Michael Borgwardt
fuente
Esto tiene mucho sentido, por lo que en realidad es solo mi falta de conocimiento sobre los logaritmos. Gracias por la respuesta simple y clara.
owwyess
Gracias @Michael Borgwardt. Cualquier posibilidad de que pueda dar el ejemplo anterior con N = 500. ¿Cómo puedo calcular eso en una calculadora con solo log base 10?
owwyess
2
@owwyess divide el resultado log10 por log10 (2)
ratchet freak
Lo siento, me había confundido y dividido con log10 (10). Gracias a todos.
owwyess
2
El factor constante mencionado en el último párrafo es aproximadamente 3.322 para la base 2. Es decir, necesita ~ 3.3 dígitos de binario para un dígito de decimal. O si prefieres, un binario de 33 dígitos es ~ 10 dígitos en decimal.
Capitán Jirafa
8

Además de la respuesta de Michael Borgwardt , el carácter de tilde delante de cada respuesta debe leerse como "proporcional a". Entonces, si dobló N (digamos, de 500 a 1000), vería que el tiempo de ejecución (o, en este caso, el número de estrellas impresas) aumentaría en un factor que sería igual a (log1000 / log 500), que es independiente de la base que usa.

Boluc Papuccuoglu
fuente
2
Siempre entendí que tilde significa aproximado, no proporcional. Esencialmente, ~es una abreviatura de ≅.
Davor Ždralo
1
Proporcional a es el ∝símbolo no ~! Se ~utiliza para indicar relaciones de equivalencia o igualdades aproximadas (consulte la página de wikipedia sobre tilde ).
Bakuriu