Mientras aprendo los conocimientos básicos del algoritmo, encuentro un acertijo sobre el cálculo de la complejidad del tiempo y el consumo de tiempo real al ejecutar los códigos.

Los códigos de demostración especifican el problema.

function calcDemo1(){
    var init = 0; 
    for(var i=0;i<40;i++){
        init += 0;
    }
    return init;
}

function calcDemo2(){
    var init = 0; 
    init += (0+1+2+3+4+5+6+7+8+9+10+11+12+13+14+15+16+17+18+19+20+21+22+23+24+25+26+27+28+29+30+31+32+33+34+35+36+37+38+39);
    return init;
}
  1. ¿La complejidad de tiempo de calcDemo1 es O (1) incluso si es un "bucle for"?
  2. En caso de que su complejidad de tiempo fuera O (1), ¿toman la misma cantidad de tiempo en el peor de los casos cuando ejecutan el código?

La pregunta relativa es aquí

0
PageYe 14 nov. 2017 a las 11:58

2 respuestas

La mejor respuesta

Ambos tienen una complejidad de tiempo constante. O(1) complejidad de tiempo.

Para el caso 1 hay un bucle for pero se ejecuta 40 veces. Entonces será de una complejidad de tiempo constante.

En el segundo caso, no hay bucle for, pero sigue siendo una adición de tiempo constante. Entonces es O(1) nuevamente.

No significa que si hay un bucle for, su complejidad no puede ser constante .

Como respuesta al comentario, sí, incluso si aumentamos el valor codificado, la complejidad del tiempo no cambiará. Seguirá siendo O(1).

3
user2736738 14 nov. 2017 a las 09:15

Complejidad temporal constante O(1) significa que la ejecución lleva la misma cantidad de tiempo, sin importar cuán grande sea la entrada.

Complejidad de tiempo lineal O(n) significa que la ejecución tarda más en el mismo grado en que aumenta el tamaño de entrada.

Sus ejemplos

Depende de lo que defina como su entrada. En mi análisis a continuación, supongo que su entrada es la cantidad de veces que se repite / agrega un número (40). Si no hay ninguna entrada, entonces cualquier código tendrá una complejidad de tiempo constante O(1).

calcDemo1 probablemente tenga una complejidad lineal porque el compilador de JavaScript no es lo suficientemente inteligente como para darse cuenta de que podría simplemente omitir el ciclo. En realidad, aumentará i 40 veces y luego agregará 0 a init 40 veces (o al menos verificará si realmente tiene que agregar algo). Por lo tanto, cada rotación del bucle en realidad lleva algo de tiempo y, digamos, un bucle 4000 veces sería 100 veces más largo que 40 veces.

calcDemo2 también tiene una complejidad lineal O(n): agregar 1 millón de números debería tomar aproximadamente 1000 veces más que solo agregar 1000 números.

0
E. Villiger 14 nov. 2017 a las 09:12