Complexidade de Tempo e Espaço - sheilaalmeida.pro.br · The Design and Analysis of Computer Algorithms , 1974 Sheila Almeida (DAINF-UTFPR-PG) Complexidade de empTo e Espaço junho

Complexidade de Tempo e Espaço

Profa. Sheila Morais de Almeida

DAINF-UTFPR-PG

junho - 2018

Sheila Almeida (DAINF-UTFPR-PG) Complexidade de Tempo e Espaço junho - 2018 1 / 43

Este material é preparado usando como referências os textos dos seguinteslivros.

Thomas H. CORMEN, Charles E. LEISERSON, Ronald L. RIVEST, Cli�ordSTEIN. Introduction to Algorithms, 2nd ed., 2001.

Alfred AHO, Je�rey HOPCROFT, John ULLMAN. The design and analysis

of computer algorithms, 1st ed., 1974.

Udi Manber. Introduction to Algorithms: a creative approach., 1st ed.,1989.


Algoritmos

Estamos interessados em avaliar a e�ciência de um algoritmo.

E�ciência

A e�ciência do algoritmo é medida em termos da quantidade de recursos(memória, tempo de execução, número de processadores, acessos a disco)que o mesmo utiliza quando é executado.

Na maioria dos casos, vamos medir a e�ciência em tempo de execução.


Modelo Computacional RAM

A análise de um algoritmo depende do modelo computacional adotado.

É de acordo com o modelo computacional que se de�ne quais são osrecursos disponíveis e quanto custam.

Modelo RAM - Random Access Machine

• Simula máquinas convencionais.

• Um único processador que executa instruções sequencialmente.

• Operações aritméticas básicas (somas, subtrações, multiplicações edivisões), atribuições e comprações são feitas em tempo constante.



x1 xnxn-1...x5x4x3x2

Programa

contador programa

fita somente de leitura (entrada)

fita somente de escrita (saída)

...v1 v3v2

...

Memória

r1

r5r4r3r2

acumulador

Fonte: A. Aho; J. Hopcroft; J. Ullman. The Design and Analysis of Computer

Algorithms, 1974



No modelo RAM o programa não é armazenado na memória, então oespaço que ele ocupa não é contabilizado no gasto de memória.

Instruções existentes em computadores reais podem ser incorporadas aomodelo RAM sem alterar a ordem de grandeza da complexidade dosproblemas1.

1A. Aho; J. Hopcroft; J. Ullman. The Design and Analysis of Computer Algorithms,

1974


Análise de Algoritmos

Para fazer uma previsão do tempo necessário para a execução de umalgoritmo em determinado modelo computacional, considerando umadeterminada instância do problema, devemos:

• Identi�car o conjunto Q das instruções computacionais básicas domodelo.

• Determinar t(q), o tempo necessário para a execução de cadainstrução q ∈ Q.

• Determinar f (q), a quantidade de vezes que cada instrução q ∈ Q éexecutada.

• Calcular o tempo total de execução:∑∀q∈Q

f (q) · t(q)



Exemplo: análise do Algoritmo de Ordenação por Inserção (Insertion Sort).

Quantas operações de comparação são executadas?Depende da instância.

Algoritmo Ordenação por Inserção

Entrada: v [1..n]; n;Para i de 2 a n faça:

j ← i − 1Enquanto j > 0 && v [i ] < v [j ] faça:

j ← j − 1t ← v [i ]Para k de i − 1 a j + 1 faça:

v [k + 1]← v [k]v [j + 1]← t



Exemplo: análise do Algoritmo de Ordenação por Inserção (Insertion Sort).

Quantas operações de comparação são executadas?Depende da instância.





v [k + 1]← v [k]v [j + 1]← t



Podemos considerar todas as instâncias possíveis!

Seria uma tarefa bastante árdua! Quantas entradas possíveis existem?

Vamos usar uma medida da entrada, que chamamos de tamanho da

entrada.

• A análise dos algoritmos será em função do tamanho da entrada.

• O tamanho da entrada é normalmente denotado por n.

• Em geral, o tamanho da entrada é uma medida da quantidade dememória necessária para armazenar a entrada.



Tamanho da entrada

• Deve-se considerar as unidades básicas das estruturas de dados queserão manipuladas pelo algoritmo:

• em uma ordenação em um vetor, o número de elementos;

• no cálculo com números muito grandes (para astronomia, porexemplo), a quantidade de dígitos dos números;

• em um grafo, a quantidade de vértices e arestas.



O algoritmo pode não se comportar exatamente da mesma forma paratodas as instâncias de tamanho n.

Nós teremos que escolher, dentre todas as instâncias possíveis, qualqueremos usar como indicativo do tempo de execução do algoritmo.



Escolha das instâncias para análise

Normalmente, considera-se:

• a entrada do melhor caso, aquela que faz com que o algoritmo executeo menor número de instruções para dar a resposta;

• a entrada de caso médio, aquela que exige um tempo de execução queé aproximadamente a média dos tempos de execução de todas aspossíveis entradas; ou

• a entrada de pior caso, aquela que faz o algoritmo demorar mais(executar mais instruções) para dar a resposta.



Sobre a entrada de melhor caso

A análise com entrada de melhor caso geralmente não representa o queocorre com o tempo de execução de um algoritmo na maior parte dos casos.

A maioria dos problemas tem uma instância para a qual a sua solução étrivial.



Sobre a entrada de caso médio

Existem alguns casos famosos em que a análise realizada com entradas decaso médio apresenta resultados bem melhores que a análise com entradasde pior caso.

Alguns problemas são intratáveis no pior caso, mas as entradas queexplicitam esse comportamento podem raramente ocorrer na prática.

• A complexidade de caso médio pode ser uma medida mais precisa daperformance desses algoritmos.




Poderia ser uma boa escolha! Mas...

O que é uma entrada do caso médio? Nem sempre é claro o que é umaentrada de caso médio.

Que parâmetros serão usados para se tirar a média?

Se não tomarmos cuidado, podemos considerar como entrada de casomédio um tipo de entrada que nunca ocorre na prática.




É difícil avaliar o desempenho de entradas de caso médio. Geralmente,exigem maior habilidade matemática.

Nós veremos alguns exemplos de análise com entradas de caso médio, masvamos nos concentrar em análises com entradas de pior caso.



Sobre a entrada de pior caso

A análise com entrada de pior caso fornece um limite superior para otempo de execução do algoritmo. Conhecer esse limite é ter uma garantiade que o algoritmo não vai demorar mais do que essa medida.

Em alguns casos, o pior caso ocorre com frequência: na busca em umbanco de dados, o pior caso é quando o dado não está no banco.



Sobre a entrada de pior caso

Frequentemente, os resultados da análise com entradas de pior caso são

muito próximos dos obtidos com entradas de caso médio ou atravésde observações experimentais.

Mesmo quando a análise com entradas de pior caso tem resultadosdiferentes da análise com entradas de caso médio, o algoritmo que tem o

melhor desempenho no pior caso também tem desempenho muito

bom com as demais instâncias.



Nós chamamos de

• Análise de pior caso, aquela que considera as instâncias de pior caso;

• Análise de caso médio, aquela que considera as instâncias de casomédio;

• Análise de melhor caso, aquela que considera as instâncias de melhorcaso.



Para o Algoritmo de Ordenação por Inserção, apresente uma instância

• de melhor caso;

• de pior caso;

• e de caso médio.







v [k + 1]← v [k]v [j + 1]← t




• de melhor caso: vetor em ordem crescente.

• de pior caso: vetor em ordem decrescente.

• e de caso médio: quando v [i ] é considerado, cada número de v [0] av [i − 1] tem 50% de chance de ser maior que v [i ] e 50% de chance deser menor que v [i ]. Para um exemplo, podemos supor:

• os números em posições de 0 a b i2c são menores que v [i ] e

• os números em posições de b i2c+ 1 a i − 1 são maiores que v [i ].




• de melhor caso: vetor em ordem crescente.

• de pior caso: vetor em ordem decrescente.

• e de caso médio: quando v [i ] é considerado, cada número de v [0] av [i − 1] tem 50% de chance de ser maior que v [i ] e 50% de chance deser menor que v [i ]. Para um exemplo, podemos supor:

• os números em posições de 0 a b i2c são menores que v [i ] e

• os números em posições de b i2c+ 1 a i − 1 são maiores que v [i ].

Ex.: 90 12 18 83 24 71 67 35 58 40.


Análise de complexidade de tempo no pior caso

Considere o Algoritmo de Ordenação por Inserção:





v [k + 1]← v [k]v [j + 1]← t



Pergunta: Quantas instruções básicas do modelo computacional RAM(operações aritméticas básicas, atribuições e comparações) são executadaspelo Algoritmo de Ordenação por Inserção, considerando uma entrada detamanho n de pior caso?





Entrada: v [1..n]; n;Para i de 2 a n faça: 2+ 3(n − 1) = 3n − 1

j ← i − 1 2(n − 1) = 2n − 2Enquanto j > 0 && v [i ] < v [j ] faça: 2

∑n−1c=1 c + (n − 1)∗

j ← j − 1 2∑n−1

c=1 c = n2 − nt ← v [i ] n − 1

Para k de i − 1 a j + 1 faça: 4n(n−1)2

+ 4(n − 1)†

v [k + 1]← v [k] 2n(n−1)2

= n2 − nv [j + 1]← t 2(n − 1) = 2n − 2

∗2∑n−1

c=1 c + (n − 1) = n(n − 1) + (n − 1) = (n + 1)(n − 1) = n2 − 1

†4n(n−1)

2+ 4(n − 1) = 2n2 + 2n − 4





Entrada: v [1..n]; n;Para i de 2 a n faça: 2+ 3(n − 1) = 3n − 1

j ← i − 1 2(n − 1) = 2n − 2Enquanto j > 0 && v [i ] < v [j ] faça: n2 − 1

j ← j − 1 2∑n−1

c=1 c = n2 − nt ← v [i ] n − 1Para k de i − 1 a j + 1 faça: 2n2 + 2n − 4

v [k + 1]← v [k] 2n(n−1)2

= n2 − nv [j + 1]← t 2(n − 1) = 2n − 2

Total: 5n2 + 8n − 11


Análise Assintótica

Ao realizar a análise do algoritmo para uma determinada instância detamanho n, encontramos uma função f (n).

f (n) é o número de instruções que são executadas para dar a resposta.

Exemplo: para o Algoritmo Insertion Sort, f (n) = 5n2 + 8n − 11.

Então, dadas as funções que determinam o número de instruções que doisalgoritmos diferentes executam para resolver o mesmo problema:

f (n) = 5n2 + 8n − 11.

g(n) = n3 + 2.

Estamos interessados em comparar essas funções para saber qual algoritmoé mais e�ciente (executa menos instruções).


Análise Assintótica

f (n) = 5n2 + 8n − 11 g(n) = n3 + 2

-50 -40 -30 -20 -10 10 20 30 40 50 60 70 80

500

1000

1500

2000

2500

3000

3500

0

f

g

Estamos interessados em comparar essas funções quando o tamanho daentrada for muito grande.



A tabela abaixo, extraída do livro "The design and analysis of computeralgorithms", de Aho, Hopcroft e Ullman, compara diferentes algoritmosconsiderando o mesmo período de tempo para a execução e o tamanho dasinstâncias que podem ser tratadas nesse prazo.



Observe que em 1 minuto o algoritmo A1 consegue resolver o problemapara uma instância de tamanho 60.000, enquanto o algoritmo A5 resolve oproblema para uma instância de tamanho 15.

Faça outras comparações!Sheila Almeida (DAINF-UTFPR-PG) Complexidade de Tempo e Espaço junho - 2018 32 / 43


Pergunta: Mas e se a gente tiver computadores muito mais potentes?

Não vamos mais precisar nos preocupar com a e�ciência dos algoritmos?



Suponha que os computadores se tornem 10 vezes mais rápidos que os dageração utilizada para as comparações da tabela anterior.

No livro de Aho, Hopcroft e Hullman, eles apresentam a seguinte tabela decomparação:



Observe que no algoritmo A4 um aumento de 10 vezes na velocidade decomputação das instruções causa um aumento de pouco mais que 2 vezesno tamanho das entradas que se pode computar.



No algoritmo A5, o aumento de 10 vezes na velocidade de computaçãoaumentou em menos de 4 unidades (não é vezes!) o tamanho dasentradas que se pode computar.



Conclusão: A complexidade do algoritmo se torna mais importante quantomaior for a velocidade de computação.


Uma nota sobre a complexidade de espaço

A Complexidade de Espaço é medida em função da quantidade de memóriaauxiliar e total necessária para a execução do algoritmo.

Na memória auxiliar não são considerados os espaços necessários para:

• o próprio programa;

• a entrada;

• e a saída.



• O armazenamento do própio programa é desconsiderado pois éindependente do tamanho da entrada.

• Os armazenamentos da entrada e da saída não são considerados pois,na comparação de diferentes algoritmos que resolvem o mesmoproblema, todos ocupam a mesma quantidade de memória paraarmazenamento da entrada e da saída.



Da mesma forma que na complexidade de tempo, pode-se fazer uma análisecom a entrada de tamanho n de melhor caso, caso médio ou pior caso.

Um algoritmo A1 que necessite de f1(n) = 10n unidades de memória é umalgoritmo com complexidade de espaço linear em função do tamanho daentrada.

Um algoritmo A2 que necessite de f2(n) = 50 unidades de memória(independente do valor de n) é um algoritmo com complexidade de espaçoconstante em função do tamanho da entrada.

Observe que se n > 5 o algoritmo A2 utiliza menos memória que oalgoritmo A1 para resolver o problema.








v [k + 1]← v [k]v [j + 1]← t



No Algoritmo de Ordenação por Inserção, independente de a entrada ser demelhor caso, caso médio ou pior caso, o espaço utilizado para memóriaauxiliar é:

• 1 inteiro, para armazenar a variável i ;

• 1 inteiro, para armazenar a variável j ;

• 1 inteiro, para armazenar a variável k ;

• e 1 inteiro, para armazenar a variável t.

Logo, o algoritmo de ordenação por inserção utiliza uma quantidade dememóra auxiliar constante (4 vezes o tamanho de um inteiro),independente do tamanho da entrada.

A função que descreve a quantidade de memória auxiliar do algoritmo deordenação por inserção é f (n) = 4 e, portanto, é constante em relação aotamanho da entrada.



No Algoritmo de Ordenação por Inserção, independente de a entrada ser demelhor caso, caso médio ou pior caso, o espaço total utilizado da memóriaé:

• 1 inteiro, para armazenar a variável i ;• 1 inteiro, para armazenar a variável j ;• 1 inteiro, para armazenar a variável k ;• 1 inteiro, para armazenar a variável t;• e n+ 1 inteiros para armazenar a quantidade de números da sequênciae quais são esses números.

O algoritmo de ordenação por inserção utiliza uma quantidade de memóratotal linear ((n + 5) vezes o tamanho de um inteiro), onde n é o tamanhoda entrada.

A função que descreve a quantidade total de memória usada pelo algoritmode ordenação por inserção é g(n) = n + 5, que é linear em função dotamanho da entrada.


Documents

Complexidade de Tempo e Espaço - sheilaalmeida.pro.br · The Design and Analysis of Computer Algorithms , 1974 Sheila Almeida (DAINF-UTFPR-PG) Complexidade de empTo e Espaço junho