PERGUNTA 4 A análise amortizada, de forma simplificada, consiste em dividir a execução de um algoritmo em tarefas e analisar o tempo médio de execu...

PERGUNTA 4 A análise amortizada, de forma simplificada, consiste em dividir a execução de um algoritmo em tarefas e analisar o tempo médio de execução dessas tarefas, para obtermos um valor correspondente ao pior caso possível de tempo de execução de um algoritmo. Utilizamos essa análise para obter o tempo de execução de um algoritmo quando: a. O tempo de execução não pode ser obtido de forma correta por meio de uma redução assintótica. b. O algoritmo necessariamente apresenta trechos recursivos. c. O algoritmo sofre influência do estado dos dados originais em sua complexidade de tempo. d. O algoritmo apresenta uma complexidade de tempo fatorial (O(n!)) ou maior. e. Necessariamente estamos analisando a complexidade de um algoritmo NP-completo.