Como medir a Complexidade de Algoritmos

” complexidade” em termos de algoritmos refere-se à forma como o involvedness da estrutura do algoritmo afeta a velocidade de execução do algoritmo , após a entrada de dados. Para avaliar a complexidade de algoritmos , os matemáticos e cientistas da computação usam Big Oh notação , que é uma técnica matemática que permite calcular quantitativamente a velocidade de execução ( complexidade ) do algoritmo. Instruções

1

Escreva o algoritmo em sua forma funcional para o tempo de execução. Cada algoritmo é diferente a este respeito, e você nunca vai ter a sua verdadeira forma — apenas uma estimativa. Você pode obter a estimativa de olhar para o código do próprio algoritmo e contando o número de unidades de tempo que leva para o algoritmo para concluir o cálculo de uma entrada de tamanho “n “. Escrever essa função como ” f ( n). ” Por exemplo, um ” loop ” que inicia em 1 e termina no n terá a função f ( n) = n como sua estimativa de tempo de execução .

2

Estimar um limite superior para f (n ) . Um limite superior é um número que f ( n) não pode passar depois de um valor grande o suficiente de n. Por exemplo , se f ( n ) = n ^ 3 + 10n + 3 , a escolha lógica para uma estimativa limite superior será c * n ^ 3 , onde c é uma constante maior do que 1 . Isto é uma escolha razoável, uma vez que c * n ^ 3 é maior que o maior prazo de f ( n).

3

Escrever o limite superior na notação matemática. Escreva f (n )

4

Prove que essa desigualdade vale para grandes valores de n . Normalmente, trata-se de resolver a desigualdade para c e verificar se o resultado é válido . No exemplo acima , utilizando álgebra produz a desigualdade c> 1 + 10 * n ^ -2 + 3 * n ^ -3 . Para n grande , os valores com expoente negativo ir a zero, deixando c> 1. Essa desigualdade é verdade, porque foi dito que era verdade quando c foi escolhido .

Se a desigualdade é , a complexidade do algoritmo é O ( estimado limite superior , sem a constante). Por exemplo , uma vez que a desigualdade realizada , a complexidade é O (n ^ 3 ) . Se a desigualdade não se sustenta , é necessário estimar um novo limite superior e executar o processo novamente.