Analise de complexidade

Análise de Complexidade
Pesquisa, Ordenação e Técnicas de Armazenamento Segundo Semestre de 2011 Prof. Fernando Aires

Complexidade
Quando queremos considerar a velocidade de um algoritmo, são várias as variáveis a serem levadas em conta:
Processador Memória RAM Linguagem Temperatura da sala Outros processos na máquina

Complexidade
Entretanto, é possível comparar a eficiência de um algoritmo com a de outro algoritmo, mesmo sem considerar os efeitos vistos. Quando falamos então apenas da eficiência do algoritmo, estamos falando de sua complexidade.

Análise do Algoritmo
Quantos vezes cada instrução do algoritmo é executada?
Analisar e descobrir em função dos laços. Laços encadeados são tratados multiplicando as execuções. Em execuções com condicionais, usa-se AV para o número de vezes que a condicional é verdadeira, e AF (letras diferentes para condicionais diferentes) para o número de vezes que a condicional é falsa.

Exemplos public static int soma (int a, int b) { int res = a+b; return res; } Passos: 1 1 T(n): 2 passos

Exemplos public static int soma (int [] vetor) { int res = 0; for(int i = 0; i < vetor.length; i++) { res+=vetor[i]; } return res; }

Passos: 1 n n.1 1 T(n): 2.n + 2

Exemplos public static int soma_pares(int [][] matriz) { int res = 0; for(int i = 0; i < vetor.length; i++) { if(vetor[i] % 2 == 0) res+=vetor[i]; } return res; }

Passos: 1 n n.Av n.Av.1 1 T(n): n + 2.n.Av + 2

Exemplo
Pior caso: todos os elementos pares (Av = 1, em média)
T(n) = 3.n + 2

Melhor caso: todos os elementos ímpares (Av = 0, em média)
T(n) = n +2

Ordens assintóticas
Qual dessas expressões é maior: n2-100 ou 5n+10? Tipicamente, quando fazemos esse tipo de análise, pensamos em números pequenos (próximos de zero).

Ordens assintóticas
Entradas pequenas não influenciam diretamente na complexidade dos algoritmos. Devemos, então, encontrar o algoritmo assintoticamente mais eficiente, ou seja, o melhor para todas as entradas, exceto