La programación es una rama de las matemáticas, específicamente es una forma de anotar la lógica en el nivel en el que puedes ver lo que está haciendo.
La notación Big O es una forma de describir cuán complejo es un problema, en promedio. Si sabe cuánto tiempo llevará, en promedio, resolver un problema de un tamaño determinado, puede calcular cuánto tiempo llevará, en promedio, resolver el mismo problema pero de cualquier tamaño. También puede usarlo para comparar métodos para resolver el mismo problema.
Ejemplo 1: Tienes dos problemas / algoritmos / métodos / lo que sea. Uno se describe como O (n), el otro se describe como O (2n). El segundo es, en promedio, dos veces más complejo que el primero, 2n es dos veces n. (Solo lo escribo de esta manera para que quede claro lo que es importante, ya que muchas anotaciones parecen francamente hasta que se separan).
Ejemplo 2: Si un algoritmo se describe como O (n), entonces si le da el doble de datos para digerir, tomará (en promedio) el doble de tiempo. Obviamente, si este es un algoritmo de clasificación y le da una lista totalmente aleatoria de 10 elementos, luego una lista totalmente ordenada de 20 elementos, terminará la segunda lista más rápido que el primero. Si le diste listas totalmente ordenadas o listas totalmente codificadas en ambas ocasiones, terminará la primera en aproximadamente la mitad del tiempo.
Esta notación realmente no importa mucho hasta que te encuentres con los problemas realmente desagradables. En algo como la computadora de vuelo de una aeronave, donde los retrasos y las variaciones en el comportamiento son algo realmente malo, querrá ver muchos programas O (1), donde todo toma aproximadamente el mismo tiempo, todo el tiempo . Eso es básicamente lo que le dice el 1, que todo lleva (más o menos) tiempo constante, sin importar cuán grande o pequeño sea el problema.
En el cifrado, donde su mayor preocupación es no permitir que alguien que no debería leer sus mensajes, quiera hacer que descifrar el código sea un problema lo más feo posible. Si la solución más simple es O (2 ^ n), entonces n no tiene que ser muy grande antes de que 2 ^ n se vuelva astronómico. Si n es lo suficientemente grande, no importa cuán rápido se vuelvan las computadoras, y no importa cuántas de ellas se unan, el cifrado es esencialmente irrompible a menos que se encuentre una solución más simple.
La otra notación es, como habrás notado, horrible.
Ok, un problema de la vida real. Tiene una enorme pila de rocas de varias formas y tamaños y desea construir un muro de piedra seca alrededor de un jardín en la azotea. Desea construir la mayor cantidad de muro posible sin romper la espalda y sin hacer que el techo se derrumbe.
Por lo tanto, desea maximizar el área de la pared (el “beneficio”) sin que el peso de la pared derrumbe el techo (tiene que estar por debajo del máximo que puede soportar el techo, que está escrito como W en la página de Wikipedia). El desafío es elegir qué piedras lograrán esto.
Otro problema de la vida real. Tú haces acero. Algo que solía hacer Inglaterra. Tienes vendedores que suministran varios minerales de hierro. Todos tienen impurezas. Los minerales baratos tienen más impurezas que los buenos y, por lo tanto, menos hierro. Usted compra por tonelada, sin importar cuánto hierro haya. Desea hacer la mayor cantidad de acero posible al precio más bajo. Por lo tanto, su “beneficio” es la cantidad de acero fabricado y su “peso” es el costo real de una tonelada de hierro real.
Digamos que un proveedor suministró mineral de hierro donde el 50% de la roca no tiene valor. Por lo tanto, debe comprar dos toneladas para obtener una tonelada de hierro. Otro proveedor suministra hierro casi puro, pero cuesta mil veces más que el de cualquier otra persona. Solo tiene que comprar una tonelada, pero cuesta una fortuna absoluta.
El problema de la mochila nos permite ser realmente elegantes y permitir que el precio del acero caiga a medida que aumenta la cantidad de acero, y el precio del mineral aumenta a medida que compra más de cada proveedor. Sin embargo, no veo mucho sentido entrar en ese nivel de detalle. Una vez que comprenda la idea básica, puede agregar los ajustes que desee.
