Análise e Projeto de Algoritmos: Tempos de Execução e Instruções de Máquina

Análise e Projeto de Algoritmos Márcia Cappelle e Hebert Coelho com slides dos Profs Humberto Longo e Hugo Nascimento Instituto de Informática Universidade Federal de Goiás 2022 INFUFG APA 20221 M Cappelle H Coelho 1 1 de 828 Tempos de execução Elementos para a determinação de tempos de execução assintóticos instruções de máquina operações instruções de controle instruções condicionais e loops funções funções recursivas INFUFG APA 20221 M Cappelle H Coelho Análise Alg Iterativos 233 264 de 828 Instruções de máquina Qualquer processador é capaz de executar um número limitado de instruções Qualquer instrução é executada em um determinado período de tempo um número inteiro de ciclos de CPU Uma linguagem assembly tem um tradução quase umaauma para instruções de máquina Linguagem de programação de baixo nível Outras linguagens de programação são consideradas de alto nível Fortran Pascal Java C C O adjetivo alto referese ao nível de abstração suportado pela linguagem INFUFG APA 20221 M Cappelle H Coelho Análise Alg Iterativos 234 264 de 828 Instruções de máquina A linguagem de programação C e C sem objetos e outras abstrações pode ser considerada como uma linguagem de programação de nível médio Há abstração mas a linguagem está intimamente ligada a recursos padrões Há uma relação direta os operadores presentes na linguagem e as instruções de máquina INFUFG APA 20221 M Cappelle H Coelho Análise Alg Iterativos 235 264 de 828 Operadores Uma vez que cada instrução de máquina pode ser executada num número fixo de ciclos podemos assumir que cada operação exige um número fixo de ciclos O tempo necessário para qualquer operador é Θ1 incluindo Recuperararmazenar variáveis na memória Atribuição de variável Operações aritméticas Operações lógicas Operações bit a bit Operações relacionais Alocar e liberar memória new delete INFUFG APA 20221 M Cappelle H Coelho Análise Alg Iterativos 236 264 de 828 Operadores Alocação e desalocação de memória são as operações mais lentas por um fator significativo Exigem a comunicação com o sistema operacional Tempo adicional necessário para chamar as rotinas de construção e destruição do objeto que usará a memória alocada INFUFG APA 20221 M Cappelle H Coelho Análise Alg Iterativos 237 264 de 828 Blocos de operações Raramente ocorrem grandes blocos de operações sem quaisquer declarações adicionais de controle Se cada operação é executada em tempo Θ1 qualquer número fixo de operações também executado em tempo Θ1 Trocar conteúdo de variáveis int temp x x y y temp Atualizar sequência de variáveis i anterior atual atual proximo proximo tabelavaloresi INFUFG APA 20221 M Cappelle H Coelho Análise Alg Iterativos 238 264 de 828 Sequéncia de blocos Tempo total de execucdo O1 On O1 O1 n 1 On template typename T void updatecapacity int delta T arrayold array 1 int capacityold arraycapacity arraycapacity delta array new Tarraycapacity for int i 0 i capacityold i On arrayi arrayoldil 1 delete arrayold 3 3 6 INFUFG APA 20221 M Cappelle H Coelho Anilise Alg Iterativos 239 264 de 828 Sequência de blocos Executar três blocos de códigos Θ1 Θn2 e Θn Tempo total Θ1 n2 n Θn2 Executar dois blocos de códigos Θn ln n e Θn15 Tempo total Θn ln n n15 Θn15 Ao considerar uma soma tomar o termo dominante INFUFG APA 20221 M Cappelle H Coelho Análise Alg Iterativos 240 264 de 828 Instruções de controle Declarações que potencialmente alteram o fluxo de execução Condicionais if switch Repetições controladas for while dowhile Dado qualquer conjunto de instruções de controle aninhadas é sempre necessário trabalhar de dentro para fora Determinar primeiro os tempos de execução das instruções mais internas e depois das demais de dentro para fora INFUFG APA 20221 M Cappelle H Coelho Análise Alg Iterativos 241 264 de 828 Instruções de controle O tempo de execução de uma instrução condicional é 1 o tempo de execução da condição de teste mais 2 o tempo de execução do bloco de instruções executado a partir do resultado do teste Na maioria dos casos o tempo de execução da condição é Θ1 1 i f c o n d i t i o n 2 3 bloco 1 de i n s t r u ç õ e s 4 5 e l s e 6 7 bloco 2 de i n s t r u ç õ e s 8 INFUFG APA 20221 M Cappelle H Coelho Análise Alg Iterativos 242 264 de 828 Instruções de controle Em alguns casos é fácil determinar qual instrução deve ser executada 1 i n t f a t o r i a l i n t n 2 3 i f n 0 4 5 r e t u r n 1 6 7 e l s e 8 9 r e t u r n n f a t o r i a l n 1 10 11 INFUFG APA 20221 M Cappelle H Coelho Análise Alg Iterativos 243 264 de 828 Instruções de controle Em outros casos é menos óbvio Ex encontrar o maior valor armazenado em uma matriz unidimensional 1 i n t findmax i n t V i n t n 2 3 max V 0 4 5 f o r i n t i 1 i n i 6 7 max V i max V i 8 9 10 r e t u r n max 11 INFUFG APA 20221 M Cappelle H Coelho Análise Alg Iterativos 244 264 de 828 Instruções de controle Se é conhecida alguma informação sobre a distribuição dos valores armazenados na matriz o que se pode concluir a respeito da atualização do valor da variável max 1 Se os valores estão ordenados ascendente a variável max será atualizada a cada iteração 2 Se os valores estão ordenadas descendente a variável max não será atualizada nenhuma vez 3 Se os valores estão estão aleatória e uniformemente distribuídos o que se pode afirmar INFUFG APA 20221 M Cappelle H Coelho Análise Alg Iterativos 245 264 de 828 Instruções de controle de loop Declaração for do C para repetição de blocos de operações 1 f o r i n t i 0 i N i 2 3 bloco de i n s t r u ç õ e s 4 Declaração equivalente 1 i n t i 0 i n i c i a l i z a ç ã o 2 w h i l e i N condição de parada 3 4 bloco de i n s t r u ç õ e s 5 i incremento 6 INFUFG APA 20221 M Cappelle H Coelho Análise Alg Iterativos 246 264 de 828 Instruções de controle de loop A inicialização o teste da condição de parada e o incremento geralmente são declarações individuais Θ1 Assim o tempo de execução de uma declaração for é Ω1 pois pelo menos a inicialização e um teste da condição de parada devem ocorrer Se o bloco de instruções dentro do for não depende da variável de controle i no exemplo abaixo o tempo de execução do for é Θnfn 1 f o r i n t i 0 i n i 2 3 bloco de i n s t r u ç õ e s é Θfn 4 Se o corpo é bloco de instruções é Ofn então o tempo de execução do for é Onfn INFUFG APA 20221 M Cappelle H Coelho Análise Alg Iterativos 247 264 de 828 Instruções de controle de loop Se o loop interno é Θn o loop externo é Θn2 1 i n t sum 0 2 f o r i n t i 0 i n i 3 4 f o r i n t j 0 j n j 5 6 sum 1 Θ1 7 8 INFUFG APA 20221 M Cappelle H Coelho Análise Alg Iterativos 248 264 de 828 Instruções de controle de loop Suponha que a cada iteração é realizada uma pesquisa linear em uma matriz 1m O loop interno é Om e portanto o loop externo é Onm 1 f o r i n t i 0 i n i 2 3 busca l i n e a r em matriz 1 m é Om 4 INFUFG APA 20221 M Cappelle H Coelho Análise Alg Iterativos 249 264 de 828 Instrucdes de controle de loop O1 se setsn Tempo condicionado fn 1 On caso contrario void Disjointsetsclear if sets n f 01 return 3 maxheight 0 a numdisjointsets n for int i 0 i n i parent i i On treeheighti 0 3 ef 9 INFUFG APA 20221 M Cappelle H Coelho Analise Alg Iterativos 250 264 de 828 Analise de declaracées de repeticdo Seo bloco de instrugdes dentro do loop depende da variavel i no exemplo abaixo e o tempo de execucdo do bloco é O fin entéo o tempo de execucdo do Joop é n1 O S0 oxrtin i0 1 for int i 0 i n i 2 3 bloco de instrucgées é Ofin 4 eS 9 INFUFG APA 20221 M Cappelle H Coelho Anilise Alg Iterativos 251 264 de 828 Analise de declaracées de repeticdo No exemplo abaixo o oop interno é O1 i1 1 2 e o loop externo é n1 n1 Q1 S14 O n 5 4 On 10 i0 1 int sum 0 2 for int i 0 i n i 3 4 for int j 0 j i Hy 5 6 sum i Jj 7 8 eS 9 INFUFG APA 20221 M Cappelle H Coelho Anilise Alg Iterativos 252 264 de 828 Análise de declarações de repetição No exemplo abaixo o bloco de instruções mais interno linha 8 é Θ1 e os loops linhas 6 4 e 2 são Θj Θi2 e Θn3 respectivamente 1 i n t sum 0 2 f o r i n t i 0 i n i 3 4 f o r i n t j 0 j i j 5 6 f o r i n t k 0 k j k 7 8 sum i j k 9 10 11 INFUFG APA 20221 M Cappelle H Coelho Análise Alg Iterativos 253 264 de 828 Sequências de instruções Bloco de instruções seguido por um outro bloco de instruções executados em série Se o primeiro bloco Ofn e o segundo é Ogn então o tempo de execução de dois blocos de código é Ofn gn Geralmente para algoritmos que não contém chamadas de função Ofn gn é simplificado para Ofn ou Ogn INFUFG APA 20221 M Cappelle H Coelho Análise Alg Iterativos 254 264 de 828 Sequências de instruções Considere os seguintes problemas relativos a pesquisar uma lista com n valores aleatórios 1 encontrar o valor máximo e 2 descobrir se a lista contém um valor específico Qual é a descrição mais apropriada para o tempo de execução dos algoritmos para os dois problemas O problema 1 exige que cada elemento da lista seja examinado Assim o algoritmo é Θn No problema 2 a procura por um valor específico pode terminar antes Por exemplo o valor procurado pode ser o primeiro da lista Assim o algoritmo é On INFUFG APA 20221 M Cappelle H Coelho Análise Alg Iterativos 255 264 de 828 Sequências de instruções Resumo Se o termo dominante é Θ então o resultado é Θ Se o termo dominante é O então o resultado é O Exemplos On On2 On4 On n2 n4 On4 On Θn2 Θn2 On2 Θn On2 On2 Θn2 Θn2 INFUFG APA 20221 M Cappelle H Coelho Análise Alg Iterativos 256 264 de 828 Funções Uma função ou subrotina é um bloco de instruções que foi isolado seja por representar operações repetidas ex funções matemáticas ou por ser um grupo de instruções específicas ex tarefas de inicialização Uma função pode ser chamada a partir de qualquer ponto de um algoritmo Para isso é necessário preparar o ambiente adequado lidar com os argumentos parâmetros da função desviar a execução do algoritmo para a função executar a função lidar com os valores de retorno limpar o ambiente utilizado INFUFG APA 20221 M Cappelle H Coelho Análise Alg Iterativos 257 264 de 828 Funções Como chamada de funções é uma tarefa comum a maioria dos processadores modernos têm instruções que executam a maior parte destes passos com uma ou poucas instruções Vamos supor que a sobrecarga necessária para fazer uma chamada de função é Θ1 Como a chamada de qualquer função requer essa sobrecarga vamos supor que é sempre Ω1 É impossível que a chamada de qualquer função gere um tempo de execução nulo INFUFG APA 20221 M Cappelle H Coelho Análise Alg Iterativos 258 264 de 828 Funções Dada uma função procn na qual o tempo de funcionamento depende de n vamos associar o tempo de execução de procn a alguma função Tprocn Como o tempo de execução de qualquer função é Ω1 vamos incluir no tempo de execução de uma função o tempo necessário para a chamada e o retorno da mesma INFUFG APA 20221 M Cappelle H Coelho Análise Alg Iterativos 259 264 de 828 Funcdes Tsetunion Gi Tyfinan O1 void Disjointsetssetunionint m int n m find m Trinam Tpinan n find n if m n return numdisjointsets if treeheightm treeheightn 1 parent n nm if treeheightm treeheightn treeheight m maxheight stdmax maxheight treeheightm 3 else parent m n 3 8 INFUFG APA 20221 M Cappelle H Coelho Anilise Alg Iterativos 260 264 de 828 Métricas de tempo de execução Os dados associados a um problemaalgoritmo podem não ser determinísticos Métricas de interesse para o tempo de execução de um algoritmo tempo de execução de melhor caso tempo de execução do caso médio tempo de execução do pior caso Em muitos casos estas métricas serão significativamente diferentes INFUFG APA 20221 M Cappelle H Coelho Análise Alg Iterativos 261 264 de 828 Métricas de tempo de execução Métricas do número de comparações realizadas na busca em uma lista linear melhor caso o primeiro elemento da lista é o elemento procurado O1 pior caso o último elemento da lista é o elemento procurado On caso médio é necessário mais informações sobre a lista de elementos INFUFG APA 20221 M Cappelle H Coelho Análise Alg Iterativos 262 264 de 828 Métricas de tempo de execucdo Suponha que o elemento procurado esta na lista cujos elementos estdo uniformemente distribuidos Sea lista 6 de tamanho n entdo ha uma chance 1 do elemento procurado estar na posicao 2 Assim podemos resumir 1 Soi lnn1 nl 4 n n 2 2 que é On eS 9 INFUFG APA 20221 M Cappelle H Coelho Analise Alg Iterativos 263 264 de 828 Métricas de tempo de execucdo Suponha uma distribuicdo diferente dos elementos na lista ha uma chance de 50 de que o elemento procurado seja o primeiro da lista para cada elemento subsequente a probabilidade é reduzida por 5 Assim h Jl Jl Doig Lig i1 i1 Logo o caso médio é O1 eS 3 INFUFG APA 20221 M Cappelle H Coelho Anilise Alg Iterativos 264 264 de 828 Livros Texto T H Cormen C E Leiserson e R L Rivest Introduction to Algorithms McGrawHill New York 1990 C H Papadimitriou U V Vazirani e S Dasgupta Algoritmos McgrawHill Brasil 2009 U Manber Algorithms A Creative Approach AddisonWesley 1989 D E Knuth The Art of Computer Programming Volume 1 Fundamental Algorithms Addison Wesley 1998 D E Knuth The Art of Computer Programming Volume 2 Sorting and Searching Addison Wesley 1998 N Ziviani Projeto de Algoritmos com Implementações em Pascal e C Editora Thomson 2a Edição 2004 INFUFG APA 20221 M Cappelle H Coelho Bibliografia 828 828 de 828