Slide - Complexidade de Algoritmos - Introdução à Computação 2 - 2023-2

1 Introdução à Computação II – 5954006 Introdução à Computação II 5954006 2. Complexidade de Algoritmos Prof. Renato Tinós Depto. de Computação e Matemática (FFCLRP/USP) 2 Introdução à Computação II – 5954006 2.1. Introdução 2.1.1. Revisão de Pseudo-Código 2.1.2. Revisão de Fluxograma 2.1.3. Uma Rápida Revisão Matemática 2.2. Análise de Algoritmos 2.2.1. Análise Experimental 2.2.2. Análise por Operações Primitivas 2.2.3. Análise do Pior Caso e do Caso Médio 2.3. Notação Assintótica 2.3.1. Notação “O” 2.3.2. Notação “” 2.3.3. Notação “” 2.3.4. Outras Notações 2.4. Análise Assintótica Principais Tópicos 3 Introdução à Computação II – 5954006 2.1.1. Revisão de Pseudo-Código • Pseudo-Código ▪ Descrição em alto nível que combina » Linguagem natural » Estruturas familiares de linguagem de programação ▪ Escrito para ser interpretado por um ser-humano, e não por um computador ▪ Mais compacto que o código na linguagem de programação ▪ Facilita a análise das estruturas de dados ou dos algoritmos 4 Introdução à Computação II – 5954006 2.1.1. Revisão de Pseudo-Código Exemplo 2.1. 5 Introdução à Computação II – 5954006 2.1.1. Revisão de Pseudo-Código • Estruturas de linguagem de programação utilizadas ▪ Expressões » Atribuição:  » Relação de igualdade: = ▪ Comandos de entrada e saída: leia(...), escreva(...) » Importante: a leitura e escrita devem ser feitas para cada variável ou elemento de vetor ▪ Declarações de Rotinas: Algoritmo (par1, ...) ▪ Chamadas de sub-rotinas: subrotina (par1, ...) ▪ Retorno de sub-rotinas: retorne... (em inglês: return...) 6 Introdução à Computação II – 5954006 2.1.1. Revisão de Pseudo-Código ▪ Estruturas de Decisão: se...então...senão... (em inglês: if...then...else... ) ▪ Estruturas de Repetição: » enquanto...faça... (em inglês: while...do... ) » repita...até que... (em inglês: repeat...until... ) » para...faça... (em inglês: for...do... ) ▪ Indexação: A [ i ] 7 Introdução à Computação II – 5954006 • Fluxograma ▪ Descrição gráfica que utiliza símbolos pré-definidos ▪ Facilita o entendimento da sequência de passo do algoritmo ▪ Pode tornar-se complexo demais quando o algoritmo é grande ▪ Outro problema é que, por permitir uma ampla liberdade na representação, pode ocorrer a utilização incorreta das estruturas de controle 2.1.2. Revisão de Fluxograma 8 Introdução à Computação II – 5954006 ➢Indica o início e o fim do algoritmo ➢Indica o sentido do fluxo de dados, sendo utilizado para conectar os demais símbolos ➢Cálculos e atribuições de valores ➢Entrada de dados ➢Saída de dados ➢Tomada de decisão, com possibilidade de desvios 2.1.2. Revisão de Fluxograma 9 Introdução à Computação II – 5954006 • Condicional 2.1.2. Revisão de Fluxograma Teste F V ... se (Teste) então ... fim se ... 10 Introdução à Computação II – 5954006 Teste Inicial Seqüência de Comandos Passo F V • Repetição 2.1.2. Revisão de Fluxograma ... para (Inicial) até (Final) com (Passo) faça (Sequência de Comandos) fim para ... (Inicial) enquanto (Teste) faça (Sequência de Comandos) (Passo) fim para ... 11 Introdução à Computação II – 5954006 2.1.3. Revisão Matemática • Logaritmos e Expoentes log b a = c  a = b c Obs: em computação, é comum não escrever o valor da base quando b=2 (Exemplo: log 1024 = 10) 12 Introdução à Computação II – 5954006 2.1.3. Revisão Matemática • Algumas propriedades de somatórios Proposição 2.1. Para: dois inteiros nm0, duas funções f(i) e g(i) e uma constante c, ( )    = = = + = + n m i n m i n m i g i f i g i f i ( ) ( ) ( ) ) ( 1 1 + = −  = m n n m i ( )  ( )  = = = n m i n m i f i c c f i 13 Introdução à Computação II – 5954006 2.1.3. Revisão Matemática • Série Aritmética Proposição 2.2. Para qualquer inteiro n1, ( )( ) 6 1 2 1 1 2 + + =  = n n n i n i ( ) 2 1 1 + =  = n n i n i ( ) 4 1 2 2 1 3 + =  = n n i n i 14 Introdução à Computação II – 5954006 • Série Geométrica Proposição 2.3. Para qualquer inteiro n0 e qualquer número real 0 < a  1 , então 2.1.3. Revisão Matemática a a a n n i i − − = + = 1 1 1 0 15 Introdução à Computação II – 5954006 2.1.3. Revisão Matemática • Definições x : maior inteiro menor ou igual a x (piso ou chão) x : menor inteiro maior ou igual a x (teto) 16 Introdução à Computação II – 5954006 2.2.1. Análise Experimental • Análise de algoritmos: prever os recursos de que o algoritmo vai necessitar ▪ Exemplos de variáveis de interesse » Memória » Largura da banda de comunicação » Hardware » Tempo de execução • Aqui vamos dar mais atenção ao tempo de execução ▪ Técnicas apresentadas no curso podem ser também utilizadas para análise de memória 17 Introdução à Computação II – 5954006 2.2.1. Análise Experimental • Recursos podem ser estudados por meio de Análise Experimental ▪ Para tanto o algoritmo deve ser implementado por meio de um programa ▪ Funções, comandos e rotinas são utilizados para mensurar a variável de interesse » Podem sem: • Implementadas • Do sistema operacional • Próprias da linguagem • De bibliotecas especializadas » Exemplo para tempo de execução (como variável de interesse) • Comandos da biblioteca <ctime> (ou time.h) em C/C++ » Pode ser interessante analisar todo o programa ou apenas parte dele 18 Introdução à Computação II – 5954006 Figura 2.1. Resultados de um estudo experimental do tempo de execução (t) para diferentes entradas (n) o : computador 1 + : computador 2 2.2.1. Análise Experimental 19 Introdução à Computação II – 5954006 • Análise experimental de algoritmos ✓Principais vantagens » Permite analisar comportamentos em situações reais » Leva em conta hardware e compiladores » Não ignora custos associados a procedimentos de “tempo fixo” 2.2.1. Análise Experimental 20 Introdução à Computação II – 5954006 • Análise experimental de algoritmos XPrincipais desvantagens » Limitado conjunto de entradas para teste » Dificuldade de comparar a eficiência de dois ou mais algoritmos » Necessidade de implementar e executar o algoritmo » Depende de hardware e compiladores • Existe outro método? ✓Métodos analíticos 2.2.1. Análise Experimental 21 Introdução à Computação II – 5954006 Comentários Finais • Referências ▪ ZIVIANI, N. (2004). “Projeto de Algoritmos”, Thomson. » Seção 1.3 ▪ T. H. CORMEN; C. E. LEISERSON; C. STEIN; R. L. RIVEST; (2002). “Algoritmos: Teoria e Prática”, Campus. » Capítulo 1 » Seção 2.2