¿Qué es una explicación intuitiva de la complejidad del tiempo de ejecución del algoritmo?

La complejidad del tiempo de ejecución es una forma muy burda de pensar sobre un algoritmo. Simplemente le dice cómo se espera que el tiempo de ejecución (o los requisitos de espacio) escalen con el tamaño de los datos procesados. Esto se expresa en notación ‘Big-O’. O simplemente significa ‘Orden’, que en este caso significa ‘una estimación muy aproximada del tiempo / espacio dada una cantidad de elementos de datos para procesar, generalmente denotada por n ‘

Entonces, un algoritmo lineal como encontrar el valor más grande en una matriz es O ( n ), lo que significa que el algoritmo tiene que mirar cada elemento de datos una vez para asegurarse de que ha encontrado el más grande. Si el número de artículos se duplica, el tiempo necesario para encontrar el más grande también se duplica.

Si tenemos un algoritmo que funciona al mismo tiempo, independientemente de la cantidad de elementos, lo llamamos O (1) o tiempo constante. Este es un ideal, porque significa que el algoritmo no está limitado por el tamaño de los datos. A veces podemos organizar previamente los datos para lograr esto, por ejemplo, usando una tabla hash perfecta para localizar un elemento de datos.

Muchos algoritmos terminan necesitando tiempo cuadrático, o [matemática] O (n ^ 2) [/ matemática]. Esto ocurre cuando para cada elemento de una matriz, por ejemplo, necesitamos mirar todos los demás elementos de la matriz. Un ejemplo es el algoritmo de clasificación de burbujas. Naturalmente, esto se considera pobre, porque el tiempo aumenta con el cuadrado de los elementos a procesar. Eso podría significar que el algoritmo se volverá inutilizable con bastante rapidez si los datos crecen. A menos que podamos estar seguros de que nuestros datos siempre serán pequeños, o no hay alternativa, a los programadores les gusta evitar algoritmos como este (o [matemática] n ^ 3 [/ matemática] o [matemática] n ^ c [/ matemática])

Uno de los peores con los que podríamos terminar es O (n!) (N factorial). Esto es similar a [matemáticas] O (n ^ n) [/ matemáticas] El problema del vendedor ambulante es de este orden si solo usamos una búsqueda de fuerza bruta. El problema de TS es encontrar la ruta más corta para visitar cada ciudad en un recorrido sin volver a visitar una ciudad y terminar en la ciudad inicial. El enfoque de la fuerza bruta es determinar cada combinación del orden de las ciudades, medir la distancia total de cada una y luego elegir la más pequeña. n es el número de ciudades. Para algunas ciudades, el enfoque de la fuerza bruta es probablemente viable, pero muy rápidamente se vuelve cada vez más inviable a medida que se agregan ciudades.

Estos son solo algunos básicos que son bastante fáciles de intuir si piensa en algunos de los algoritmos que exhiben estos comportamientos. Los más complejos como O (log n), que se exhibe mediante una búsqueda binaria en una lista ordenada, también son razonablemente fáciles de intuir si comprende el algoritmo y aprecia que, en todos los casos, está implícito el registro de base 2. Este es un buen rendimiento, porque el registro de un número crece mucho más lentamente que el número mismo.

Si necesitamos realizar algo equivalente a una búsqueda binaria, pero a la vez en cada elemento de una lista, terminamos con O (n log n), que se exhibe en varios algoritmos de ordenación.

Oh, este es probablemente más fácil de lo que esperas.

La complejidad de tiempo de un algoritmo es la cantidad de tiempo que necesita para resolver un problema de un tamaño determinado.

¡Eso es todo al respecto! 🙂 Realmente!

Sin embargo, si intenta analizar la complejidad del tiempo de un algoritmo, se encuentra con problemas, porque no todas las computadoras son igual de rápidas. Por lo tanto, no puede decir “este algoritmo resolverá problemas de tamaño 1000 en exactamente un segundo”, solo puede decir, “este algoritmo resolverá este problema exacto de tamaño 1000 en exactamente un segundo en tal y tal máquina”. Lo cual no es muy útil para saber.

Entonces, todo el negocio complicado con notación big-O, etc., es hacer declaraciones generalizables sobre uh, cuánto tiempo necesita un algoritmo para resolver un problema de un tamaño determinado.

Piense en el entrenamiento de circuito, un tipo de régimen de ejercicio en el que tiene muchos ejercicios diferentes que hacer, y hace uno por un minuto más o menos, luego pase al siguiente.

Nuestro programa es toda la rutina. Digamos que hay 5 ejercicios diferentes que debes hacer, y estamos haciendo una serie por ejercicio, y cada serie es de un minuto. Por lo tanto, tiene un entrenamiento de cinco minutos con 5 ejercicios diferentes, realizados de forma lineal (cada ejercicio se realiza una vez, y hay un orden).

Ahora consideremos que queremos hacer más series. Si todavía estamos haciendo 5 ejercicios, pero haciendo dos series de cada uno, y dejamos n = 5, ahora estamos haciendo 2n = 10 ejercicios. Esto es como un bucle que atravesamos dos veces.

Manteniendo n = 5, ahora queremos hacer cada ejercicio n veces, o la cantidad de veces que hay ejercicios. Esto significa que estamos haciendo n ^ 2 conjuntos, o 25 conjuntos en total.

Hay más formas en que podemos aumentar la cantidad de series / ejercicios que estamos haciendo. Considere que comenzamos con un conjunto y un ejercicio. Cada vez que completamos las series de un ejercicio, agregamos un nuevo ejercicio y duplicamos el número de series, hasta que alcancemos un número predeterminado de ejercicios que estamos haciendo.

La idea de la complejidad del tiempo de ejecución es esencialmente comprender cuántas operaciones está realizando un algoritmo / programa (por simplicidad, suponga que todas las operaciones toman aproximadamente la misma cantidad de tiempo), lo que a menudo se reduce a analizar cosas como bucles.