Complejidad de un algoritmo

> Tutorial de LeekScript

Idea general

Para estimar la cantidad de operaciones que consumirá una función o un algoritmo, es útil tener una idea de la relación entre el tamaño de los argumentos que se le dan, o el tamaño de un parámetro, y el número máximo de operaciones realizadas. . Esto se llama complejidad algorítmica.

Comencemos con un ejemplo simple: un bucle for.

para (var i=0; i N, tenemos f(n) < K xg(n).*

Muy bien, ahí tienes, tengo las grandes palabras. ¿Qué significa realmente esta definición? Que la función f crece "no más rápido" que g cuando n crece. f puede ser mayor que g, pero la razón de los dos siempre es menor que un cierto número (el K de la definición). Apliquemos esto al código: tomemos como una función (matemática) f el número máximo de operaciones realizadas por una determinada pieza de código, dado el tamaño de su entrada. Buscamos encontrar una función simple g tal que f(n)=O(g(n)). Aproximadamente equivale a medir el mayor número de veces que las instrucciones básicas se repetirán en el código (el costo de estas instrucciones se esconde debajo de la alfombra: es la K de la definición).

Ejemplos

Uf. Pasemos a los ejemplos, lo veremos más claro. Volvamos a nuestro bucle for de antes:

para (var i=0; i<n; i++){ say("Soy una zanahoria"); }

Si observamos f el número máximo de operaciones realizadas por este fragmento de código, hemos visto que f(n) era aproximadamente igual a 30 x n, más el pequeño costo del ciclo. En efecto, la instrucción say se repite n veces, lo que tiene un costo constante de 30 operaciones. Por tanto, podemos decir que f está dominada por la función g(n)=n. Así, tenemos f(n)=O(n). También decimos que este fragmento de código está "en O(n)".

¿Y la función de intersección de arreglos de tamaño n? Hemos visto que consume aproximadamente n² x (número de operaciones push + costo de comparar dos elementos). Suponiendo que el costo de inserción es constante (lo cual es falso, pero no quiero entrar en detalles de inmediato), tenemos, al establecer K = (número de operaciones de inserción + costo de comparar dos elementos), que el costo de la función de intersección está dominada por n²: decimos que la función de intersección está "en O(n²)".

Así, la notación O permite medir el crecimiento del costo según el tamaño de la entrada: la función de intersección tendrá un costo que crece "a la misma velocidad" que n² (siendo n el tamaño de las matrices).

Interés en Leekwars

Esta noción es interesante porque a menudo podemos estimar con bastante facilidad un O(g(n)) y, por lo tanto, saber si una función comenzará a costar mucho cuando aumente la entrada. es por ejemplo uti