Para la complejidad del tiempo, Aditya Joshi ha escrito una gran respuesta:
La respuesta de Aditya Joshi a ¿Cuáles son algunas formas fáciles de entender y calcular la complejidad temporal de los algoritmos?
¡Aquí estoy escribiendo sobre la notación Big-O y algunos detalles adicionales que hacen referencia a la respuesta de Aditya Joshi!
La definición más simple que puedo dar para la notación Big-O es esta:
La notación Big-O es una representación relativa de la complejidad de un algoritmo.
Hay algunas palabras importantes y elegidas deliberadamente en esa oración:
- pariente: solo puedes comparar manzanas con manzanas. No puede comparar un algoritmo para hacer multiplicación aritmética con un algoritmo que ordena una lista de enteros. Pero una comparación de dos algoritmos para realizar operaciones aritméticas (una multiplicación, una adición) le dará algo significativo;
- representación: Big-O (en su forma más simple) reduce la comparación entre algoritmos a una sola variable. Esa variable se elige en base a observaciones o suposiciones. Por ejemplo, los algoritmos de clasificación generalmente se comparan en función de las operaciones de comparación (comparación de dos nodos para determinar su orden relativo). Esto supone que la comparación es cara. Pero, ¿qué pasa si la comparación es barata pero el intercambio es costoso? Cambia la comparación; y
- complejidad: si me lleva un segundo ordenar 10.000 elementos, ¿cuánto tiempo me llevará ordenar un millón? La complejidad en este caso es una medida relativa a otra cosa.
Vuelve y vuelve a leer lo anterior cuando hayas leído el resto.
El mejor ejemplo de Big-O que se me ocurre es hacer aritmética. Toma dos números (123456 y 789012). Las operaciones aritméticas básicas que aprendimos en la escuela fueron:
- adición;
- sustracción;
- multiplicación; y
- división.
Cada uno de estos es una operación o un problema. Un método para resolverlos se llama algoritmo .
La suma es la más simple. Alinea los números hacia arriba (a la derecha) y agrega los dígitos en una columna escribiendo el último número de esa suma en el resultado. La parte ‘decenas’ de ese número se traslada a la siguiente columna.
Supongamos que la suma de estos números es la operación más costosa en este algoritmo. Es lógico que para sumar estos dos números juntos tengamos que sumar 6 dígitos (y posiblemente llevar un séptimo). Si sumamos dos números de 100 dígitos, tenemos que hacer 100 sumas. Si agregamos dos números de 10,000 dígitos, tenemos que hacer 10,000 sumas.
¿Ves el patrón? La complejidad (que es el número de operaciones) es directamente proporcional al número de dígitos n en el número mayor. Llamamos a esto O (n) o complejidad lineal .
La resta es similar (excepto que puede que necesite pedir prestado en lugar de llevar).
La multiplicación es diferente. Alinee los números, tome el primer dígito en el número inferior y multiplíquelo por turnos contra cada dígito en el número superior y así sucesivamente a través de cada dígito. Entonces, para multiplicar nuestros dos números de 6 dígitos, debemos hacer 36 multiplicaciones. Es posible que necesitemos hacer hasta 10 u 11 adiciones de columna para obtener el resultado final también.
Si tenemos dos números de 100 dígitos, necesitamos hacer 10,000 multiplicaciones y 200 sumas. Para dos números de un millón de dígitos necesitamos hacer un billón (1012) de multiplicaciones y dos millones de sumas.
A medida que el algoritmo se escala con n cuadrado , esto es O (n2) o complejidad cuadrática . Este es un buen momento para presentar otro concepto importante:
Solo nos importa la parte más significativa de la complejidad.
El astuto puede haberse dado cuenta de que podríamos expresar el número de operaciones como: n2 + 2n. Pero como viste en nuestro ejemplo con dos números de un millón de dígitos cada uno, el segundo término (2n) se vuelve insignificante (representa el 0.0002% del total de operaciones en esa etapa).
Uno puede notar que hemos asumido el peor de los casos aquí. Si bien multiplicamos números de 6 dígitos si uno de ellos es de 4 dígitos y el otro es de 6 dígitos, entonces solo tenemos 24 multiplicaciones. Aún así, calculamos el peor de los casos para esa ‘n’, es decir, cuando ambos son números de 6 dígitos. Por lo tanto, la notación Big-O trata sobre el peor de los casos de un algoritmo
La guía telefónica
El siguiente mejor ejemplo que se me ocurre es la guía telefónica, normalmente llamada White Pages o similar, pero variará de un país a otro. Pero estoy hablando del que enumera a las personas por apellido y luego iniciales o nombre, posiblemente dirección y luego números de teléfono.
Ahora, si estuviera instruyendo a una computadora para que busque el número de teléfono de “John Smith” en una guía telefónica que contiene 1,000,000 de nombres, ¿qué haría? Ignorando el hecho de que podrías adivinar qué tan lejos comenzaron las S (supongamos que no puedes), ¿qué harías?
Una implementación típica podría ser abrirse a la mitad, tomar el número 500,000 y compararlo con “Smith”. Si resulta ser “Smith, John”, tenemos mucha suerte. Mucho más probable es que “John Smith” aparezca antes o después de ese nombre. Si es después, dividimos la última mitad de la guía telefónica a la mitad y repetimos. Si es antes, dividimos la primera mitad de la guía telefónica a la mitad y repetimos. Y así.
Esto se llama búsqueda binaria y se usa todos los días en la programación, ya sea que se dé cuenta o no.
Entonces, si desea encontrar un nombre en una guía telefónica de un millón de nombres, puede encontrar cualquier nombre haciendo esto como máximo 20 veces. Al comparar algoritmos de búsqueda, decidimos que esta comparación es nuestra ‘n’.
- Para una guía telefónica de 3 nombres, se necesitan 2 comparaciones (como máximo).
- Para 7 se necesita como máximo 3.
- Para 15 se necesitan 4.
- …
- Para 1,000,000 se necesitan 20.
Eso es asombrosamente bueno, ¿no?
En términos de Big-O, esto es O (log n) o complejidad logarítmica . Ahora el logaritmo en cuestión podría ser ln (base e), log10, log2 o alguna otra base. No importa que siga siendo O (log n) al igual que O (2n2) y O (100n2) siguen siendo O (n2).
En este punto, vale la pena explicar que Big O puede usarse para determinar tres casos con un algoritmo:
- Mejor caso: en la búsqueda de la guía telefónica, el mejor caso es que encontremos el nombre en una comparación. Esto es O (1) o complejidad constante ;
- Caso esperado: Como se discutió anteriormente, esto es O (log n); y
- Peor caso: esto también es O (log n).
Normalmente no nos importa el mejor caso. Estamos interesados en el peor y esperado caso. A veces uno u otro de estos será más importante.
De vuelta a la guía telefónica.
¿Qué sucede si tiene un número de teléfono y desea encontrar un nombre? La policía tiene una guía telefónica inversa, pero tales búsquedas se niegan al público en general. ¿O son? Técnicamente, puede revertir la búsqueda de un número en una guía telefónica ordinaria. ¿Cómo?
Empiezas con el primer nombre y compara el número. Si es un partido, genial, si no, pasas al siguiente. Tiene que hacerlo de esta manera porque la guía telefónica no está ordenada (de todos modos, por número de teléfono).
Entonces para encontrar un nombre:
- Mejor caso: O (1);
- Caso esperado: O (n) (por 500,000); y
- Peor caso: O (n) (por 1,000,000).
El vendedor ambulante
Este es un problema bastante famoso en informática y merece una mención. En este problema tienes N ciudades. Cada una de esas ciudades está vinculada a una o más ciudades por una carretera de cierta distancia. El problema del vendedor ambulante es encontrar el recorrido más corto que visita cada ciudad.
¿Suena simple? Piensa otra vez.
Si tiene 3 ciudades A, B y C con carreteras entre todos los pares, entonces podría ir:
- A → B → C
- A → C → B
- B → C → A
- B → A → C
- C → A → B
- C → B → A
Bueno, en realidad hay menos que eso porque algunos de estos son equivalentes (A → B → C y C → B → A son equivalentes, por ejemplo, porque usan los mismos caminos, justo al revés).
En la actualidad hay 3 posibilidades.
- Lleva esto a 4 ciudades y tienes (iirc) 12 posibilidades.
- Con 5 son 60.
- 6 se convierte en 360.
Esta es una función de una operación matemática llamada factorial . Básicamente:
- 5! = 5 × 4 × 3 × 2 × 1 = 120
- 6! = 6 × 5 × 4 × 3 × 2 × 1 = 720
- 7! = 7 × 6 × 5 × 4 × 3 × 2 × 1 = 5040
- …
- 25! = 25 × 24 ×… × 2 × 1 = 15,511,210,043,330,985,984,000,000
- …
- 50! = 50 × 49 ×… × 2 × 1 = 3.04140932 × 1064
Entonces, el gran problema del vendedor ambulante es O (n!) O complejidad factorial o combinatoria .
Cuando llegas a 200 ciudades, no hay suficiente tiempo en el universo para resolver el problema con las computadoras tradicionales.
Algo sobre lo que pensar.
Tiempo polinomial
Otro punto del que quería hacer una mención rápida es que cualquier algoritmo que tenga una complejidad de O (na) se dice que tiene una complejidad polinómica o que se puede resolver en el tiempo polinómico .
O (n), O (n2), etc. son todos tiempo polinomial. Algunos problemas no se pueden resolver en tiempo polinómico. Ciertas cosas se usan en el mundo debido a esto. La criptografía de clave pública es un excelente ejemplo. Es computacionalmente difícil encontrar dos factores primos de un número muy grande. Si no fuera así, no podríamos usar los sistemas de clave pública que usamos.
Complejidad del tiempo:
¿Cuánto tiempo dura este programa de clasificación? Posiblemente demore mucho tiempo en entradas grandes (es decir, muchas cadenas) hasta que el programa haya completado su trabajo y dé una señal de vida nuevamente. A veces tiene sentido poder estimar el tiempo de ejecución antes de iniciar un programa. ¡Nadie quiere esperar una guía telefónica ordenada por años! Obviamente, el tiempo de ejecución depende del número n de las cadenas que se ordenarán. ¿Podemos encontrar una fórmula para el tiempo de ejecución que depende de n?
Al observar de cerca el programa, notamos que consta de dos bucles for anidados. En ambos bucles, las variables van de 0 a n, pero la variable interna comienza desde donde se encuentra la externa. Un if con una comparación y algunas tareas no ejecutadas necesariamente residen dentro de los dos oops. Una buena medida del tiempo de ejecución es el número de comparaciones ejecutadas. [11] En la primera iteración tienen lugar n comparaciones, en la segunda n-1, luego n-2, luego n-3, etc. Entonces, las comparaciones 1 + 2 +… + n se realizan en conjunto. De acuerdo con la conocida fórmula de suma gaussiana, estas son exactamente 1/2 · (n-1) · n comparaciones.
La figura ilustra esto. El área filtrada corresponde al número de comparaciones ejecutadas. Aparentemente corresponde aprox. a la mitad del área de un cuadrado con una longitud lateral de n. Por lo tanto, equivale a aproximadamente 1/2 · n2. ¡Hasta que el programa haya terminado! Todo esto es causado por la expresión n2. Uno dice: Ordenar por búsqueda mínima tiene una complejidad cuadrática . Esto nos da un presentimiento de que este método no es adecuado para grandes cantidades de datos porque simplemente lleva demasiado tiempo.
Por lo tanto, sería una falacia decir: “Por mucho dinero, simplemente compraremos una máquina que sea dos veces más rápida, luego podemos clasificar el doble de cadenas (al mismo tiempo)”. Consideraciones teóricas sobre el tiempo de ejecución ofrecen protección contra tales falacias.
El número de instrucciones (máquina) que ejecuta un programa durante su tiempo de ejecución se denomina complejidad en informática. Este número depende principalmente del tamaño de la entrada del programa, es decir, aproximadamente del número de cadenas que se ordenarán (y su longitud) y del algoritmo utilizado. Entonces, aproximadamente, la complejidad de tiempo del programa “ordenar una matriz de n cadenas por búsqueda mínima” se describe mediante la expresión c · n2. c es una constante que depende del lenguaje de programación utilizado, de la calidad del compilador o intérprete, de la CPU, del tamaño de la memoria principal y del tiempo de acceso a la misma, del conocimiento del programador y, por último, pero no menos en el algoritmo en sí, que puede requerir instrucciones de máquina simples pero que también requieren mucho tiempo. (En aras de la simplicidad, hemos dibujado el factor 1/2 aquí en c). Entonces, si bien se puede reducir c mejorando las circunstancias externas (y por lo tanto a menudo invirtiendo mucho dinero), el término n2, sin embargo, siempre permanece sin alterar.
Así que si
f ∈O ( g ) significa que f crece como máximo tan rápido como g , asintóticamente y hasta un factor constante; Piense en ello como un ≤. f ∈ o ( g ) es la forma más estricta, es decir, <.
f ∈Ω ( g ) tiene el significado simétrico: f crece al menos tan rápido como g . ω es su primo más estricto. Puede ver que f ∈Ω ( g ) es equivalente a g ∈O ( f ).
f ∈Θ ( g ) significa que f crece casi tan rápido como g ; formalmente f ∈O ( g ) ∩Ω ( g ). f ∼ g (igualdad asintótica) es su forma más fuerte. A menudo queremos decir Θ cuando usamos O.
Observe cómo O ( g ) y sus hermanos son clases de función . Es importante ser muy consciente de esto y de sus definiciones precisas que pueden diferir dependiendo de quién está hablando al hacer “aritmética” con ellos. Al probar cosas, tenga cuidado de trabajar con su definición precisa. Existen muchas definiciones para los símbolos de Landau (todas con la misma intuición básica), algunas de las cuales son equivalentes en algunos conjuntos de funciones pero no en otros.
Lectura sugerida:
- ¿Cuáles son las reglas para los signos de igualdad con big-O y little-o?
- Funciones de clasificación por crecimiento asintótico
- ¿Cómo se relacionan O y Ω con el peor y el mejor caso?
- Notación O grande anidada
- Definición de Θ para funciones negativas
- ¿Cuál es el significado de O ( m + n )?
¿Se considera O (mn) crecimiento “lineal” o “cuadrático”?
- Sumas de términos Landau revisitados
- ¿Qué significa O grande como término de una relación de aproximación?
Resumen :
Complejidad espacial de un algoritmo es el espacio total ocupado por el algoritmo con respecto al tamaño de entrada.
Qué significa eso?
Esencialmente, esa es la cantidad de memoria que necesita un algoritmo.
A menudo, hay un compromiso espacio-tiempo en un problema, donde nos comprometemos; es decir, no podemos tener tanto tiempo de cómputo bajo como bajo consumo de memoria, por lo que, dependiendo del algoritmo, elegimos si el tiempo de cómputo bajo es esencial o el consumo de memoria.
Notaciones asintóticas:
Las anotaciones asintóticas se usan para expresar el componente principal del costo de un algoritmo particular usando unidades idealizadas de trabajo computacional.
¿Para qué lo usamos?
Un problema puede tener numerosas soluciones algorítmicas, pero queremos elegir el mejor algoritmo para la tarea, por lo que tomamos dos soluciones y juzgamos cuánto tiempo se ejecutarán, el que tenga el menor tiempo de ejecución (menor complejidad de tiempo) es nuestro ganador.
Tipos de anotaciones asintóticas:
- Notación Big-O: se utiliza para expresar el límite superior del tiempo de ejecución de un algoritmo, es decir, nos dice el peor de los casos (el tiempo más largo) que un algoritmo podría tardar en completarse. Se denota como
si y solo si existen constantes k y n tales que,
- Notación Big-Omega : exactamente lo contrario de Big-O, se utiliza para expresar el límite inferior del tiempo de ejecución de un algoritmo, es decir, nos dice el mejor caso (el menor tiempo) que un algoritmo tardaría en completarse. Se denota como
si y solo si existen constantes k y n tales que,
- Notación Theta : una combinación de Big-O y Big-Omega, tiene un límite inferior y un límite superior. Esto determina el caso promedio del tiempo de ejecución de un algoritmo. Se denota como
si y solo si existen constantes j, k y n tales que,
Espero que esto ayude. Gracias.
