Me pregunto si en una pregunta se habla sobre el tiempo de ejecución de un algoritmo, ¿significa lo mismo que Complejidad de tiempo o si hay alguna diferencia entre los dos?Diferencia entre Complejidad de tiempo y Tiempo de ejecución
Analizar un algoritmo es determinar la cantidad de recursos (como tiempo y almacenamiento) necesarios para ejecutarlo. La mayoría de los algoritmos están diseñados para trabajar con entradas de longitud arbitraria. Por lo general, el efficiency or running time of an algorithm se establece como una función que relaciona la longitud de entrada con el number of steps (time complexity) o las ubicaciones de almacenamiento (complejidad del espacio).
El tiempo de ejecución es el tiempo que tarda un programa en ejecutarse. La complejidad del tiempo es una descripción del comportamiento asintótico del tiempo de ejecución ya que el tamaño de entrada tiende a infinito.
Puede decir que el tiempo de ejecución "es" O (n^2) o lo que sea, porque esa es la forma idiomática de describir las clases de complejidad y la notación de gran O. De hecho, el tiempo de ejecución no es una clase de complejidad, es una duración o una función que le da la duración. "Ser O (n^2)" es una propiedad matemática de esa función, no una caracterización completa de la misma. El tiempo exacto de ejecución puede ser 2036 * n^2 + 17453 * n + 18464 ciclos de CPU, o lo que sea. No es que a menudo necesite saberlo con tanto detalle, y de todos modos podría depender tanto de la entrada real como del tamaño de la entrada.
"Como el tamaño de entrada tiende a infinito", es cierto. – CodeYogi
La complejidad del tiempo y el tiempo de ejecución son dos cosas completamente distintas.
La complejidad del tiempo es un concepto teórico completo relacionado con los algoritmos, mientras que el tiempo de ejecución es el tiempo que un código tardaría en ejecutarse, en absoluto teórico.
Dos algoritmos pueden tener la misma complejidad de tiempo, digamos O (n^2), pero uno puede tardar el doble de tiempo de ejecución que el otro.
El tiempo de ejecución de un algoritmo en una entrada en particular es el número de operaciones primitivas o “pasos” ejecutados. Es conveniente para definir la noción de paso para que sea tan independiente de la máquina como posible.
Ahora desde Wikipedia
... tiempo de la complejidad de un algoritmo cuantifica la cantidad de tiempo empleado por un algoritmo para funcionar como una función de la longitud de la cadena que representa la entrada.
complejidad Tiempo comúnmente se estima mediante el recuento del número de operaciones elementales realizadas por el algoritmo, donde un operación elemental tiene una cantidad fija de tiempo para llevar a cabo.
Observe que ambas descripciones enfatizan la relación entre el tamaño de la entrada y el número de operaciones primitivas/elementales.
Creo que esto deja en claro que ambos hacen referencia al mismo concepto.
En la práctica, sin embargo, encontrará que la jerga de la empresa rara vez coincide con la terminología académica, p., toneladas de personas trabajan haciendo optimización de código, pero rara vez resuelven optimization problems.
"Tiempo de funcionamiento" se refiere al algoritmo bajo consideración:
Otro algoritmo podría ser capaz de resolver el mismo problema asintóticamente más rápido, es decir, con menos tiempo de ejecución.
"La complejidad del tiempo" por otro lado es inherente al problema en consideración. Se define como el menos tiempo de ejecución de cualquier algoritmo que resuelva dicho problema.
Lo mismo se aplica a distincting otras medidas de costo algorítmica como la memoria, #processors, el volumen de la comunicación, etc.
(de Blum Speedup teorema demuestra que el tiempo "menos" puede, en general, no sea posible ...)
Depende completamente del contexto en el que se utilizó el término. Cuando su jefe pregunta por qué el "tiempo de ejecución" fue de 3 horas, no está hablando de complejidad algorítmica. Cuando su profesor pregunta cuál es el "tiempo de ejecución" de un algoritmo, probablemente no le está pidiendo que salga de su cronómetro y lo mida. –