Complexidade de um algoritmo

> Tutorial LeekScript

Ideia geral

Para estimar a quantidade de operações que uma função ou um algoritmo irá consumir, é útil ter uma ideia da relação entre o tamanho dos argumentos dados a ela, ou o tamanho de um parâmetro, e o número máximo de operações realizadas . Isso é chamado de complexidade algorítmica.

Vamos começar com um exemplo simples: um loop for.

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

Tudo bem, lá vai você, eu tenho as palavras grandes para fora. O que essa definição realmente significa? Que a função f cresce "não mais rápido" do que g à medida que n aumenta. f pode ser maior que g, mas a razão entre os dois é sempre menor que um certo número (o K da definição). Vamos aplicar isso ao código: vamos tomar como função (matemática) f o número máximo de operações executadas por um determinado trecho de código, dado o tamanho de sua entrada. Procuramos encontrar uma função simples g tal que f(n)=O(g(n)). Isso equivale aproximadamente a medir o maior número de vezes que as instruções básicas serão repetidas no código (o custo dessas instruções é, portanto, varrido para debaixo do tapete: é o K da definição).

Exemplos

Ufa. Vamos aos exemplos, veremos com mais clareza. Vamos voltar ao nosso loop for anterior:

for (var i=0; i<n; i++){ diga("Eu sou uma cenoura"); }

Se observarmos f o número máximo de operações executadas por esse trecho de código, veremos que f(n) era aproximadamente igual a 30 x n, mais o pequeno custo do loop. De fato, a instrução say é repetida n vezes, o que tem um custo constante de 30 operações. Podemos então dizer que f é dominado pela função g(n)=n. Assim, temos f(n)=O(n). Também dizemos que esse trecho de código está "em O(n)".

E a função de interseção de arrays de tamanho n? Vimos que ele consome aproximadamente n² x (número de operações push + custo de comparação de dois elementos). Supondo que o custo push seja constante (o que é falso, mas não quero entrar em detalhes agora), temos, ao definir K = (número de operações push + custo de comparação de dois elementos), que o custo de a função de interseção é dominada por n²: dizemos que a função de interseção é “em O(n²)”.

Assim, a notação O permite medir o crescimento do custo de acordo com o tamanho da entrada: a função de interseção terá um custo que cresce "na mesma velocidade" que n² (com n o tamanho dos arrays).

Interesse em Leekwars

Essa noção é interessante porque muitas vezes podemos estimar facilmente um O(g(n)) e, assim, saber se uma função começará a custar muito caro quando a entrada aumentar. é por exemplo uti