Análise de Algoritmos: Funções Recursivas e Selection Sort

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 Funcdes Recursivas Fatorial Fatorial int factorial int n if n1 1 return 1 else Tn101 return n factorial n 1 O tempo de execucdo desta fundo pode ser expresso como e1 sen 1 Tn Tn101 sen1 eS 9 INFUFG APA 20221 M Cappelle H Coelho Analise Alg Recursivos 272 286 de 828 Funções recursivas Tn Tn 1 Θ1 Tn 1 c1 Tn 2 c1 c1 Tn 2 2c1 Tn 3 3c1 Tn k kc1 INFUFG APA 20221 M Cappelle H Coelho Análise Alg Recursivos 273 286 de 828 Funções recursivas para k n 1 Tn Tn n 1 n 1c1 T1 n 1c1 c2 c1n c1 c1n c2 c1 Logo podese concluir que Tn On Tn Θn INFUFG APA 20221 M Cappelle H Coelho Análise Alg Recursivos 274 286 de 828 Funções recursivas Selection sort 1 v o i d s e l e c t i o n S o r t i n t array i n t n 2 i f n 1 3 r e t u r n 4 5 i n t posn 0 6 i n t max a r r a y posn 7 8 f o r i n t i 1 i n i 9 i f a r r a y i max 10 posn i 11 max a r r a y posn 12 13 14 15 i n t tmp a r r a y n 1 16 a r r a y n 1 a r r a y posn 17 a r r a y posn tmp 18 19 s e l e c t i o n S o r t array n 1 20 INFUFG APA 20221 M Cappelle H Coelho Análise Alg Recursivos 275 286 de 828 Funcdes recursivas Selection sort caso especial O or 1 itens devem ser classificados if nm 1 1 return assume que o primeiro elemento é o maior int posn 0 ae int max arrayposn 3 8 INFUFG APA 20221 M Cappelle H Coelho Analise Alg Recursivos 276 286 de 828 Funções recursivas Selection sort Procura entre os demais elementos Se um maior é encontrado atualiza a posição e o valor do maior Θn for int i 1 i n i if arrayi max posn i max arrayposn INFUFG APA 20221 M Cappelle H Coelho Análise Alg Recursivos 277 286 de 828 Funções recursivas Selection sort Troca a posição do maior com o último Θ1 int tmp arrayn 1 arrayn 1 arrayposn arrayposn tmp Classifica os demais elementos Tn 1 selectionSort array n 1 INFUFG APA 20221 M Cappelle H Coelho Análise Alg Recursivos 278 286 de 828 Funcdes recursivas Selection sort Relacdo de recorréncia e1 sen 1 Tn Tn10n sen 1 Versdo simplificada 1 sen 1 Tn Tn1n sen1 eS 9 INFUFG APA 20221 M Cappelle H Coelho Analise Alg Recursivos 279 286 de 828 Funcdes recursivas Selection sort Relacdo de recorréncia TnTn14n Tn2n1n Tn2nn1 Tn3nn1n2 n n n T1 i145iy i2 i2 i1 nn 1 2 Qn eS 9 INFUFG APA 20221 M Cappelle H Coelho Analise Alg Recursivos 280 286 de 828 Funções recursivas Busca binária Código C não recursivo 1 i n t buscaBin i n t V i n t chave i n t n 2 3 i n t esq 0 Limite esquerdo 4 i n t d i r n1 Limite d i r e i t o 5 i n t meio 6 7 w h i l e esq d i r 8 9 meio esq d i r 2 10 i f chave V meio 11 r e t u r n meio Encontrou elemento 12 e l s e 13 i f chave V meio 14 d i r meio 1 15 e l s e 16 esq meio 1 17 18 r e t u r n 1 Não encontrou 19 INFUFG APA 20221 M Cappelle H Coelho Análise Alg Recursivos 281 286 de 828 Funções recursivas Busca binária Código C recursivo buscaBin V chave 0 n 1 1 i n t buscaBin i n t V i n t chave i n t esq i n t d i r 2 3 i n t meio 1 Não encontrou 4 5 i f esq d i r 6 7 meio esq d i r 2 8 i f chave V meio 9 meio buscaBin V chave esq meio 1 10 e l s e 11 i f chave V meio 12 meio buscaBin V chave meio 1 d i r 13 e l s e encontrou 14 15 16 r e t u r n meio 17 INFUFG APA 20221 M Cappelle H Coelho Análise Alg Recursivos 282 286 de 828 Funcdes recursivas Busca binaria Verificar o elemento central Se ndo é o desejado verificar 4 esquerda ou a direita do elemento central conforme o caso Relacdo de recorréncia e1 sen 1 T 0 sen1 Versdo simplificada C2 sen l Tn a Sot T a sen1 eS 9 INFUFG APA 20221 M Cappelle H Coelho Analise Alg Recursivos 283 286 de 828 Funcdes recursivas Busca binaria nm 2B 0 n Tn T 5 c n T 35 2 n T 2c1 Quando 5 1lilIgn Tn T1algn oclgn o8 63 INFUFG APA 20221 M Cappelle H Coelho Analise Alg Recursivos 284 286 de 828 Funções recursivas Busca binária Lembrese que Se lim n fn gn c e 0 c então fn Θgn Logo lim n c1 lg n c2 ln n lim n c1lg n ln n lim n c2 ln n c1 lim n ln n ln 2 ln n 0 c1 lim n 1 ln 2 c11 4427 Portanto Tn Θln n INFUFG APA 20221 M Cappelle H Coelho Análise Alg Recursivos 285 286 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