Análise de complexidade algoritmica

Razões para análise algorítmica:
→prever o seu desempenho (performance)
→comparar algoritmos
→estabelecer garantias para o algoritmo (T(N)<=Tmax)
T(N)=tempo de execução dum algoritmo com input size=N
→perceber a base teórica subjacente
→evitar bugs de performance

Técnicas algorítmicas:
→dividir e conquistar
→programação dinâmica

Exemplo:
Procurar um valor num determinado vector
Int procuraValor (Int *v,Int n, Int val)
{Int i;
    For(i=0;i<n;i++)
       If(v[i]==val)
            Return i;
Return -1;
}

Num algoritmo com tamanho de n dados ,temos 3 situações:

→melhor caso(best case ): situação mais favorável em termos de configuração dos dados na entrada T(N)=B(N)
→pior caso (worst case): situação mais desfavorável T(N)=W(N)
→caso médio (average case): e determinado estatisticamente o número médio de operações básicas T(N)=A(N)

Int s=0; // está instrução e executada 1 vez
For(i=0;i<n;i++)
S=+v[i] Única Instrução que acede ao vector(modelo de custo usado nesta análise poderia por exemplo: considerar apenas as instruções se acesso ao vector(ler ou escrever))

estas instruções são executadas n vezes