Karteikarten

Complexidade de algoritimos

Rafael Miranda Portugiesisch 11 Karten

Karten in diesem Stapel (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