ESTRUTURAS DE DADOS
Complexidade
Algoritmo
Algoritmo é qualquer procedimento
computacional bem definido que toma algum
valor ou conjunto de valores como entrada e
produz algum valor ou conjunto de valores
como saída.
Portanto, um algoritmo é uma sequência de
passos computacionais que transformam a
entrada na saída.
Algoritmo
Ex.: Entrada: Uma sequência de n números
<a1, a2, ..., an>
Saída: Uma permutação <x1, x2,..., xn>
da sequência de entrada, tal que
x1≤x2≤...≤xn
Algoritmo
Um algoritmo é dito correto se, para cada
instância de entrada, ele para com a saída
correta.
A medida habitual de eficiência é a velocidade,
isto é, quanto tempo um algoritmo leva para
produzir seu resultado. Porém, existem alguns
problemas para os quais não se conhece
nenhuma solução eficiente. Um subconjunto
desses problemas denomina-se NP-Completo.
Algoritmo
Por que os problemas NP-Completos são
interessantes?
Embora não tenha sido encontrado nenhum
algoritmo eficiente para um problema NP-
Completo, ninguém jamais provou que não é
possível existir um algoritmo eficiente para
esse fim.
Algoritmo
O conjunto de problemas NP-Completos tem
a propriedade notável de que, se existe um
algoritmo eficiente para qualquer um deles,
então existem algoritmos eficientes para
todos.
◦ Ex.: Caixeiro Viajante.
Algoritmo
Os computadores podem ser rápidos, mas não
são infinitamente rápidos. A memória pode ser
de baixo custo, mas não é gratuita. Assim, o
tempo de computação é um recurso limitado
bem como o espaço na memória.
Esses recursos devem ser usados de forma
sensata e algoritmos eficientes em termos de
tempo ou espaço ajudarão nesse sentido.
Algoritmo
Eficiência:
◦ Algoritmos criados para resolver o mesmo
problema muitas vezes diferem de forma
drástica em sua eficiência.
◦ Ex.: ordenação por inserção leva um tempo
aproximadamente igual a c1n2 para ordenar n
itens, em que c1 é uma constante que não
depende de n.
◦ Ex.: ordenação por intercalação leva um
tempo aproximadamente igual c2nlog(n)
Algoritmo
A ordenação por inserção normalmente tem
um fator constante menor que a ordenação
por intercalação e assim c1<c2.
Os fatores constantes podem ser muito
menos significativos no tempo de execução
que a dependência do tamanho da entrada n.
Algoritmo
Ex.: O problema consiste em ordenar um
arranjo de um milhão de números
Suponha que o computador A seja o mais
rápido e execute a ordenação por inserção, e
o computador B, mais lento, execute a
ordenação por intercalação.
Algoritmo
O computador A executa um bilhão de
instruções por segundo e o computador B
executa apenas dez milhões de instruções por
segundo; assim o computador A é 100 vezes
mais rápido que o computador B em
capacidade bruta de computação.
Algoritmo
A codificação por inserção possui 2n2
instruções para ordenar n números.
A ordenação por intercalação tem um
código de 50nlog(n) instruções.
A → 2(106)2 /(109) instruções-
segundo = 2000 segundos
B → 50 106 log2(106)/107 = 100
segundos
Algoritmo
Ordenação por Inserção
para j←2 até tamanho[A] faça
chave←A[j];
i←j-1;
enquanto i>0 e A[i]> chave faça
A[i+1]←A[i];
i←i-1;
A[i+1]←chave;
Algoritmo
Análise do Algoritmo
Algoritmo de Inserção (A) custo vezes
for j = 2 to comprimento de A c1 n
chave = A[j]; c2 n-1
i = j - 1; c3 n-1
n
while i > 0 e A[i] > chave c4
∑tj
j=2
n
A[i + 1] = A[i]; c5
∑ (t j−1)
j=2
i = i – 1; c6 n
∑ (t j−1)
j=2
A[i+1] = chave; c7 n-1
Algoritmo
Melhor caso?
Pior caso?
Algoritmo
Análise do algoritmo no melhor caso
T(n)=c1.n+c2(n-1)+c3(n-1)+c4∑nj=2tj+
c5∑nj=2(tj-1)+c6∑nj=2(tj-1)+c7(n-1)
T(n)=c1.n+c2(n-1)+c3(n-1)+c4(n-1)+
+c7(n-1)
T(n)=(c1+c2+c3+c4+c7)n-(c2+c3+c4+c7)
Complexidade: (n)
Algoritmo
Análise do algoritmo no pior caso
T(n)=c1.n + c2(n-1) + c3(n-1)+ c4∑nj=2tj +
c5∑nj=2(tj-1) + c6∑nj=2(tj-1) + c7(n-1)
Sendo:
∑nj=2tj=[n(n+1)/2]-1 e ∑nj=2(tj-1)=n(n-1)/2
Logo temos:
T(n)=C1.n + C2.(n-1) + C3.(n-1) + C4.
((n(n+1)/2)–1) + C5.(n(n-1)/2) + C6.(n(n-
1)/2) + C7.(n-1)
Algoritmo
Análise do algoritmo no pior caso
T(n)=(C4/2+c5/2+c6/2)n2+(c1+c2+c3+c4/2-c5/2-
c6/2+c7)n-(c2+c3+c4+c7)
Complexidade: O(n2)
Slides baseados no livro
Thomas H. Cormen, Charles E. Leiserson,
Ronald L. Rivest, Clifford Stein,
Algoritmos, Campus, 3ª edição, 2012.