Flashcards
Complexidade de algoritimos
Cards in this deck (11)
- 1Algoritmo que chama a si mesmo direta ou indiretamenteAlgoritmos Recursivos
- 2Algoritmos que dividem o problema em vários subproblemas menores que são resolvidos recursivamenteDivisão e Conquista
- 3Normalmente possuem um custo equivalente aos algoritmos iterativos, que requerem o uso de estruturas auxiliares (pilhas,etc)Algoritmos Recursivos
- 4Tem como vantagem uma implementação mais simples, normalmente direta a partir da definição do problemaDivisão e Conquista
- 5Pode ser usada para estabelecer limites superiores e inferiores para a recorrênciaMétodo da Substituição
- 6Tem como possíveis problemas: Estimação da solução; Cuidados na aplicação da induçãoMétodo da Substituição
- 7Monta‐se uma árvore onde cada nó representa o custo de um subproblemaMétodo da Árvore de Recursão
- 8Fornece uma 'receita' para resolver recorrências da forma T(n)=aT(n/b)+f(n)Método Mestre
- 9São equações de igualdade ou desigualdade que define uma função em termos de seu valor para entradas menoresRelações de Recorrência
- 10É um algoritmo para ordenação de dados simples e compacto, normalmente implementado utilizando recursão.MergeSort
- 11Algoritimo para encontrar a sublista contígua de maior soma a partir de uma lista de números.Subarranjo