El tiempo de ejecución de un algoritmo depende del número de iteraciones que tiene que pasar, o el número de veces que se ejecuta el algoritmo antes de llegar a la salida final y deseada.
Por ejemplo, dado un conjunto ordenado de enteros, se nos pide que proporcionemos un algoritmo con comprobaciones si el número x está presente en el conjunto o no. Luego hay 2 algoritmos más utilizados para esto:
- BÚSQUEDA LINEAL : Busca linealmente todos y cada uno de los elementos de una matriz desde el principio verifica el valor del índice de la matriz con x. Esta iteración continúa hasta que no se encuentra el número x. Entonces, la complejidad del tiempo en el peor de los casos sería O (n) donde n es el número de elementos de matriz. Lo que significa que, si la computadora tarda C segundos en ejecutar una declaración, en el peor de los casos el tiempo de ejecución sería [matemático] nC [/ matemático] segundos.
- BÚSQUEDA BINARIA: en esto, la matriz se divide en 3 partes, una parte izquierda, una parte derecha y el elemento central. El elemento del medio se verifica con x y si se encuentra igual muestra la salida. De lo contrario, si x es más pequeño que el elemento del medio, el algoritmo verifica la parte izquierda de la matriz de la misma manera. Si x es mayor que la parte media, entonces verifica la parte derecha. En este caso, la complejidad del tiempo en el peor de los casos es O (lg n). Suponiendo que la computadora tarda C segundos en ejecutar una instrucción, el tiempo de ejecución total en este caso para el peor de los casos sería [matemática] C.lg (n) [/ matemática] segundos.
Entonces, en estos dos casos, para cualquier número de entradas, el número de iteraciones en la búsqueda binaria siempre será menor que el número de iteraciones en la búsqueda lineal. Por lo tanto, el tiempo de ejecución del algoritmo de búsqueda binaria tomaría menos tiempo que el algoritmo de búsqueda lineal,
- ¿Cuál es el enfoque algorítmico para encontrar el primer entero positivo que falta si se proporciona una matriz entera sin clasificar en O (n) complejidad de tiempo y espacio constante?
- Se me pide que lea datos de un archivo .txt en una matriz y que haga cosas con esa información (encontrar promedio, encontrar número de elementos, encontrar valores máximos / mínimos). ¿Cómo se puede hacer esto en Java?
- ¿Dónde debo comenzar una estructura de datos?
- ¿Es una buena idea modelar otras estructuras de datos después de STD :: Vector?
- Cómo crear un sistema de clasificación que dependa de tres variables (nivel, resultado y tiempo) cuanto más altas sean las dos primeras, mejor, mientras que por un tiempo, un valor menor es mejor
Espero que ayude.
