0
153
ViewsTratando de entender la razón de esta complejidad del tiempo
Estoy tratando de calcular la complejidad temporal de estos dos algoritmos. El libro al que me refiero especifica estas complejidades temporales de cada uno.
A) Algoritmo A: O(nlogn)
int i = n; while (i > 0) { for (int j = 0; j < n; j++) System.out.println("*"); i = i / 2; }B) Algoritmo B: O(n)
while (n > 0) { for (int j = 0; j < n; j++) System.out.println("*"); n = n / 2; } Puedo ver cómo algo. A es O(nlogn) . El bucle for es O(n) y el bucle while es O(logn). Sin embargo, no veo cómo AlgoB tiene una complejidad de tiempo de O (n). Esperaba que fuera O(nlogn) también. Cualquier ayuda sería apreciada.
2 answers
Answer question0
El algoritmo B está imprimiendo la mitad de los inicios en cada iteración. Suponga que n=10, entonces:
n=10 -> 10* n=5 -> 5* n=2 -> 2* n=1 -> 1* En total se imprimen 18*. Imprimirás n + n/2 + n/4 + ... + n/(2^i) estrellas. ¿ i valoro? Es igual al número de pasos necesarios para que n se convierta en 0. En otros términos, es el exponente al que se debe elevar 2 para producir n : log_2(n) . Obtienes la suma en la imagen:
Que se puede aproximar a O(n).
0
Veamos el Algoritmo B desde un punto de vista matemático.
El número de * impreso en el primer ciclo es n . El número de * impreso en cada bucle subsiguiente es como máximo n /2. Esa relación de recurrencia conduce a la secuencia:
n + n/2 + n/4 + n/8 + ...Si esta fuera una secuencia infinita, entonces la suma podría representarse mediante la fórmula n /(1 - r ), donde r es el factor entre los términos. En este caso, r es 1/2, por lo que la sucesión infinita tiene una suma de 2( n ).
Su algoritmo ciertamente no continuará para siempre, y cada vez que se repite, puede estar imprimiendo menos de la mitad de las estrellas del bucle anterior. El número de estrellas impresas es por lo tanto menor o igual a 2( n ).
Debido a que los factores constantes se eliminan de la complejidad del tiempo, el algoritmo es O (n).
Este concepto se denomina complejidad amortizada , que promedia el costo de las operaciones en un ciclo, incluso si algunas de las operaciones pueden ser relativamente costosas. Consulte esta pregunta y la página de Wikipedia para obtener una explicación más detallada de la complejidad amortizada.