Cita:
Empezado por roman
Pues yo creo que sí que se ejecutarán en el mismo tiempo. Cada vuelta del ciclo de cinco instrucciones se ejecutará cinco veces más lento que una vuelta del ciclo de una instrucción, con lo cual, realmente no se gana nada.
// Saludos
|
Pues allí está el dilema y quizá una de las confusiones y errores cuando se habla de complejidad computacional. Por algo yo he dicho "tiempo" entre comillas. En realidad lo que indica la complejidad computacional es la tasa de crecimiento y la cantidad de operaciones involucradas.
El tiempo está dado por diversos factores, mayormente externos, y es lo que al final se simboliza con una constante, por lo general simbolizada por c.
Cuando comento la diferencia entre T(n) y T(n/5) estoy diciendo simplemente que el segundo crece 5 veces más lento. Por lo cual le permite recibir una entrada mayor
al mismo costo. Para igualar las condiciones de T(n) la entrada que necesita debe ser 5 veces mayor. Si ambos algoritmos se prueban en un mismo equipo, con las mismas condiciones iniciales, etc. se tiene c * T(n) y c * T(n/5). Allí claramente se ve que el segundo caso es preferible al primero.
Pero en vista a a que tanto T(n) y T(n/5) tienen el mismo órden, directamente se habla en términos de asíntota: O(n), y luego las constantes c se "ajustan". Para el caso de T(n/5) la constante c es en realidad c/5.
¿Me explico?
Saludos,