Questão de Algoritmos e Estrutura de Dados — Algoritmos — IF-MG 2024
Algoritmos e Estrutura de Dados›Algoritmos
Código
qg240144
Banca
IF-MG
Órgão
IF-MG
Ano
2024
Nível
Superior
Cargo
PROFESSOR EBTT - Informática - Itabirito
O algoritmo para resolver o problema da Torre de Hanói pode ser definido pela seguinte função recursiva:T(n) = 2T(n − 1) + 1, com T(0) = 1, onde n representa o número de discos.Esse algoritmo resolve o problema movendo os discos entre três pinos de acordo com as regras do jogo.Diante dessa definição, qual seria a ordem de complexidade do algoritmo?
AO(n²)
BO(2ⁿ)
CO(n log n)
DO(log n)
EO(n)
Revelar gabarito e comentário▾
GabaritoB — O(2ⁿ)
Comentário gerado por IA. É um apoio ao estudo, ancorado em fontes, mas pode conter imprecisões — confira sempre na fonte oficial (lei, súmula, edital e gabarito da banca). Encontrou um erro? Use “Reportar”.
Torre de Hanói - Complexidade
Gabarito: letra B. A recorrência T(n) = 2T(n-1) + 1, com T(0) = 1, resulta em uma solução fechada exponencial: T(n) = 2^{n+1} - 1, que pertence à classe O(2ⁿ). Nenhuma das outras alternativas (polinomiais ou logarítmicas) representa o crescimento do número de movimentos.
A recorrência pode ser resolvida por telescopagem ou por substituição. Expandindo:
Como T(0) = 1, temos T(n) = 2ⁿ + (2ⁿ - 1) = 2^{n+1} - 1. Portanto, o número de movimentos cresce exponencialmente com o número de discos, justificando a complexidade O(2ⁿ).
Alternativa A — ❌ Incorreta
O( n² ) é uma complexidade polinomial quadrática. Torre de Hanói requer muito mais operações: para n=10, 2^{11}-1 = 2047 movimentos, enquanto n² = 100. Portanto, não representa o crescimento real.
Alternativa B — ✅ Correta ⟵ GABARITO
O(2ⁿ ) reflete a explosão exponencial do número de movimentos (2^{n+1}-1), confirmada pela recorrência dada. É a resposta correta.
Alternativa C — ❌ Incorreta
O(n log n) é típica de algoritmos de ordenação eficientes (mergesort, heapsort). A recorrência da Torre de Hanói não se encaixa nesse padrão; sua árvore de recursão dobra a cada nível, gerando 2ⁿ folhas.
Alternativa D — ❌ Incorreta
O(log n) é sublinear e aparece em algoritmos como busca binária. A Torre de Hanói exige pelo menos 2ⁿ - 1 movimentos, muito superior a log n.
Alternativa E — ❌ Incorreta
O(n) é linear. Mesmo para poucos discos, o número de movimentos cresce muito mais que linearmente: n=3 → 7 movimentos; n=4 → 15; n=5 → 31.
PEGA ESSA DICA!
Ao analisar recorrências, sempre expanda os primeiros termos ou use o teorema mestre. A recorrência T(n) = aT(n-1) + b com a>1 leva a complexidade exponencial O(aⁿ). Memorize esse padrão: Torre de Hanói é o exemplo clássico de O(2ⁿ).