Diverso

Complejidad temporal: por qué algunos algoritmos se ejecutan durante miles de millones de años

Complejidad temporal: por qué algunos algoritmos se ejecutan durante miles de millones de años


We are searching data for your request:

Forums and discussions:
Manuals and reference books:
Data from registers:
Wait the end of the search in all databases.
Upon completion, a link will appear to access the found materials.

Este es el tercer artículo de una serie de siete partes sobre algoritmos y computación, que explora cómo usamos números binarios simples para impulsar nuestro mundo. El primer artículo, Cómo funcionan los algoritmos en el mundo en el que vivimos, se puede encontrar aquí.

Si observa una visualización de diferentes algoritmos de clasificación trabajando en un conjunto de datos, se vuelve muy obvio, muy rápidamente, que algunos son mucho mejores que otros. Donde un algoritmo lleva segundos para terminar, otro tomará minutos incluso con pequeños conjuntos de datos. Afortunadamente, no necesitamos ver el algoritmo en funcionamiento para saber si el algoritmo puede hacer el trabajo rápidamente o si colapsará bajo el peso de su entrada. Eso es lo que Notación Big O es para, y nos puede decir de un vistazo si el Complejidad del tiempo de un algoritmo significa que lo obtendremos en unos pocos horas o miles de millones de años.

¿Qué es la complejidad del tiempo?

En términos más formales, complejidad del tiempo es la medida de cuánto tardará un algoritmo en producir un resultado, relativo al tamaño de su entrada. Prácticamente, es el tasa de crecimiento en el número de operaciones necesario para producir un resultado para cada unidad adicional de entrada.

En el primer artículo de esta serie, describí un sencillo algoritmo de suma. Para calcular el suma de todos los números entre los números pags y q, Declaré otra variable, ry configúrelo en cero. Luego agregué pags a r, luego agregué p + 1 a r, luego p + 2, y así sucesivamente hasta que finalmente agregué q sí mismo a r, momento en el que me detuve y devolví el resultado, r, que celebró el suma.

¿Cuántas operaciones requerirá esto, sin saber cuál será el tamaño de entrada final, usando solo las variables abstractas? pags y q? Lo que realmente estamos haciendo es ejecutar un lazo donde cada iteración aumenta pags por exactamente 1 y lo agrega r. En realidad, así es como se ve nuestro algoritmo cuando se presenta de manera algo más formal:

1. dejar r = 0
2. mientras pags es <= a q
3. r=pags+r
4. pags = pags+1
5. volver r

Cuando se presenta así en lo que llamamos pseudocódigo, resulta mucho más fácil ver cuántas operaciones se necesitarán. Baje los pasos número por número y cuente las operaciones. La primera es una instrucción, por lo que es una sola operación. La segunda línea, sin embargo, es diferente. Los ciclos como este se repiten hasta que se cumple la condición, en este caso, una vez pags es mayor que q. Entonces sabemos que estamos incluyendo q y pags en el suma, entonces el número de iteraciones a través de esto lazo es igual a q - (p - 1), Cuál es el tamaño de entrada para nuestro algoritmo.

Pero esa es solo la cantidad de veces que iteramos a través del ciclo, también tenemos que contar las operaciones dentro de él, que es donde agregamos pags y r y asignar el resultado de r y luego agregamos pags y 1 y luego asigne el resultado a pags. Entonces actuamos dos operaciones para cada iteración, y aquí están q - (p - 1)iteraciones. Todo lo que tenemos que hacer ahora es multiplicar 2 operaciones y q - (p - 1)iteraciones Llegar 2 * (q - (p - 1)) operaciones para todo el bucle. Sume las operaciones en 1. y 5., lo que nos da un recuento final de 2 * (q - (p - 1)) + 2 operaciones para este algoritmo.

Esta es una función lineal ya que no hay exponentes, por lo que la tasa de crecimiento porque nuestro algoritmo de suma es directamente vinculado a la entrada tamaño, que llamamos complejidad de tiempo lineal. Como regla general, cualquiera que sea el término de orden más alto en una fórmula que defina nuestra complejidad temporal es lo que caracteriza su crecimiento en el tiempo, por lo que tomamos el término de orden más alto y descartamos el resto, dejando q - (p - 1), que vamos a llamada norte por simplicidad.

La complejidad del tiempo lineal puede parecer ineficaz cuando se visualizan tamaños de entrada de miles de millones, pero el tiempo lineal no es tan malo. Aunque podemos hacerlo mejor.

Sabemos desde hace mucho tiempo que el suma de todaslos números desde 1 y q viene dado por la fórmula (q * (q + 1)) / 2. También sabemos que elpropiedad conmutativa de la suma nos dice que el resultado de (p-1 * (p)) / 2 extraído de (q * (q + 1)) / 2 simplemente corta la parte de la suma que incluye todo, desde 1 a pags-1, dejándo el suma de los números de pags a q detrás, que es exactamente lo que queremos.

Este algoritmo, dependiendo de cómo esté codificado, no debería tomar más de tres operaciones. Dado que las operaciones matemáticas directas como esta son exactamente las cosas que las computadoras hacen mejor que los humanos, podríamos encadenar las fórmulas en una sola expresión matemática, y el procesador la asimilará tan fácilmente como lo haría si la dividiéramos en trozos más pequeños, pero nos ceñiremos a tres operaciones por el momento.

1. p = (p-1 * (p)) / 2
2. q
= (q * (q + 1)) / 2
3. regreso ( q -pags )

No bucles, solo un número constante de operaciones que no cambian, sin importar la diferencia entre pags y q es. Este algoritmo siempre tomará tres operaciones para realizar, por eso lo llamamos complejidad de tiempo constante.

Ahora, si no sabías cuál es tu tamaño de entrada iba a ser cuando diseñabas un algoritmo, ¿qué algoritmo vas a usar entre estos dos? Obviamente, el segundo, porque algoritmos de tiempo constante son esencialmente un Almuerzo libre computacional en lo que a input se refiere. Así como nosotros aumentar proporcionalmente nuestro programa para manejar mas datos, su tiempo de ejecución no cambiará apreciablemente, mientras que sabemos que nuestro primer algoritmo crecerá exactamente tanto como nuestra entrada, lo que podría ser un valor de miles de millones o más. Por supuesto, la complejidad de tiempo constante no siempre significa que sea más eficiente, pero en este caso es la que queremos.

Antes de que nos sentáramos a escribir un línea de código, ya averiguamos qué algoritmo era la mejor opción para nuestra entraday nunca tuvimos que ejecutarlo para saber qué tan bien funciona. Por eso usamos complejidad del tiempo, simplemente no hay tantas herramientas que sean tan efectivas en calificar la eficiencia de los algoritmos.

¿Qué es la notación Big O?

Tenemos una forma especial de anotar esta eficiencia para facilitar las cosas, algo que llamamos Notación Big O. Simplemente pon, Notación Big O representa el algoritmoeficiencia correr a través de su peor de los casos. Si tuvieras que buscar un nombre en un directorio leyendo todos los nombres hasta encontrar el correcto, el peor de los casos es que el nombre que quieres es la última entrada en el directorio. Esto significa que tendría que leer todo el directorio de norte nombres para llegar al que quieras. Entonces decimos que este algoritmo es O (norte), dónde norte es el término de orden más alto en nuestra fórmula de operaciones.

Hay otros Grandes anotaciones Para el mejor caso y caso promedio, pero lo que realmente importa es el peor de los casos; ésas son las que pueden hacer fallar su computadora, o peor aún, tu carro o tu avion. Van directo al corazón del por qué complejidad del tiempo importa y señala por qué algunos algoritmos simplemente no puede resolver un problema sin tomar unos miles de millones de años para hacerlo.

Entonces, ¿cómo usamos Notación Big O? El cuadro de arriba muestra cómo estos diferentes Notaciones Big O mirar en la práctica, con el eje x siendo tu aporte y tu eje y el tiempo necesario para terminar. Para obtener más detalles, encontrará una lista rápida de todos los Notaciones Big O eso importa por ahora y el complejidad del tiempo ellos representan:

* O (1): Complejidad de tiempo constante- Este es el pase libre efectivamente computacional del que hablamos antes. Esto no significa necesariamente que sea más rápido. Solo significa que el complejidad del tiempo no está relacionado con el tamaño de la entrada.

* O (log n): Complejidad de tiempo logarítmico- Estos son más comunes cuando se usa un estrategia de divide y vencerás en un conjunto de datos, donde cada operación descarta una gran parte de la entrada que ha descartado por no tener la solución. El ejemplo clásico es buscar una palabra en un diccionario: abrir al azar, verificar en qué sección de letras se encuentra, luego ignorar la parte en la que sabe que su palabra no estará y subdividir y descartar recursivamente las secciones restantes hasta encontrar tu palabra.

* En): Complejidad de tiempo lineal- Este fue nuestro algoritmo de suma desde el principio.

* O (n log n): Complejidad de tiempo lineal- Realizar una transformada rápida de Fourier es una O (n log n) algoritmo, como es un Mergesort.

* En2): Complejidad de tiempo cuadrático- Esto generalmente se encuentra siempre que tenga bucles anidados. En nuestro primer algoritmo, si tuviéramos un segundo ciclo dentro del primero, la función habría desarrollado una complejidad de tiempo cuadrática.

* EnC, c> 1): Complejidad del tiempo polinomial- Complejidad del tiempo polinomial es muy importante porque es mas o menos representa el límite superior en que computadora clásica puede resolver en una cantidad de tiempo práctica.

* Jefenorte, n> 1, c> 1): Complejidad de tiempo exponencial- Aquí es donde empiezas a obtener Algoritmos de miles de millones de años. En cualquier momento un unidad de entrada te hace duplicar el número de operaciones realizadas relativo al número que se realiza si la entrada esn-1, tienes complejidad de tiempo exponencial. El ejemplo más común que usa la mayoría de la gente es intentar enumerar cada posible subconjunto de un conjunto, pero Fuerza bruta un Clave de cifrado de 128 bits generalmente se incluye en esta categoría.

* ¡En!): Complejidad del tiempo factorial- Estos son algoritmos que probablemente podrían ejecutarse hasta la muerte por calor del Universo con un tamaño de entrada moderadamente grande de unos pocos miles. Siempre que tenga algo como "de cuántas maneras diferentes puede organizar esta secuencia", tiene un problema de permutación y la fuerza bruta para llegar a una respuesta requiere crear ¡norte! valores diferentes, que viene dado por el resultado de: n * (n - 1) * (n - 2) * ... * 3 * 2 * 1. Estos son los algoritmos que corren casi en paralelo al eje y en el diagrama de arriba.

Por qué no podemos simplemente idear mejores algoritmos

No es por falta de intentos. Todo el campo de informática teórica se trata de tratar de encontrar el máximo algoritmo eficiente para un problema dado, pero a veces simplemente no sabemos las matemáticas. Y no solo tú y yo, estamos hablando de ganadores de la medalla de Field que se han enfrentado a algunos problemas como el O (2norte) y ¡En!) y su conjetura es tan buena como la nuestra.

Hay un catálogo completo de problemas que aún no tenemos las matemáticas para resolver (lo analizaremos más hacia el final de la serie), pero estos problemas actúan como puntos de estrangulamiento que crean ineficiencias en los negocios, la investigación científica y otros. áreas administrativas, y hay mucha gente esperando que estos problemas finalmente se resuelvan. Incluso se han ofrecido premios muy lucrativos a cualquiera que pueda resolver algunas de estas cosas, pero hasta ahora nadie ha podido hacerlo y algunos de estos problemas han estado ahí durante décadas.

La razón por la cual computadoras clásicas no puede resolver estos problemas de manera eficiente tampoco está integrado en los circuitos de la máquina; cada instrucción que se le da debe completarse antes de que pueda comenzar con la siguiente. Los sistemas multinúcleo o las máquinas multiprocesadores pueden acelerar las cosas, pero probablemente aún necesite uno o dos billones de años para obtener un resultado después de juntar todos nuestros procesadores y soltarlos en un ¡En!) problema donde norte fue algo como 500.

Los ingenieros informáticos han visto venir esto durante décadas, pero ahora finalmente estamos llegando al final de la línea de lo que podemos sacar de un computadora clásica. Simplemente no puedes hacer estos las operaciones van más rápido, y por naturaleza, pueden solo realice una operación a la vez. Si tiene un algoritmo que requiere quintillones de operaciones para completar, un computadora clásica tiene que llevar a cabo todas esas operaciones en orden. En ese punto, el tiempo que lleva obtener un resultado simplemente se convierte en una cuestión de matemáticas y física. Si vamos a resolver estos problemas que tienen complejidad de tiempo exponencial o mayor, luego algo más es necesario.

La buena noticia es que sabemos que es posible, en al menos un caso, para encontrar un algoritmo lo suficientemente eficiente como para encontrar la respuesta a uno de estos O (2norte) problemas en complejidad de tiempo polinomial. Si se puede hacer una vez, entonces es posible volver a hacerlo; solo se necesita eludiendo todo el asunto de la "física".

El cuarto artículo de nuestra serie sobre algoritmos y computación, Cómo el algoritmo de Peter Shor condena el cifrado RSA al fracaso, se puede encontrar aquí.


Ver el vídeo: The Big O notation (Junio 2022).


Comentarios:

  1. Darcy

    Estimado administrador! Puede escribir información sobre su blog en mi tablero de mensajes.

  2. Neil

    Has dado en el blanco. Algo también está bien en esto, estoy de acuerdo contigo.

  3. Native American

    Hay un sitio sobre un tema interesante de usted.

  4. Arashizilkree

    Lo siento, eso ha interferido... Entiendo esta pregunta. Vamos a discutir. Escribe aquí o en PM.

  5. Oegelsby

    Lo siento, pero en mi opinión, estás equivocado. Puedo demostrarlo.Escríbeme en PM, te habla.



Escribe un mensaje