Questão de Algoritmos e Estrutura de Dados — Algoritmos — FGV 2024
Algoritmos e Estrutura de Dados›Algoritmos
Código
fg077362
Banca
FGV
Órgão
CVM
Ano
2024
Nível
Superior
Cargo
Analista - Perfil 8 - TI / Sistemas e Desenvolvimento - Tarde
O cálculo da complexidade computacional é essencial para verificar a viabilidade do algoritmo. Observe o código a seguir, em Python, para o problema da torre de Hanoi.def hanoi(n, o, d, a):if n==1:print("D1 de "+o+" p/ "+d)else:hanoi(n-1, o, a, d)print("D"+str(n)+" de "+o+" p/ "+d)hanoi(n-1, a, d, o)A complexidade desse algoritmo no pior caso é:
AO(2n );
BO(n);
CO(n log n);
DO(n² );
EO(log n).
Revelar gabarito e comentário▾
GabaritoA — O(2n );
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 Computacional
Gabarito: letra A. O algoritmo recursivo da Torre de Hanói possui complexidade O(2^n) no pior caso. A relação de recorrência é T(n) = 2T(n-1) + 1, com T(1)=1, cuja solução fechada é T(n) = 2^n - 1 movimentos – crescimento exponencial em relação ao número de discos. O conteúdo de apoio (descrição do problema) confirma que o número mínimo de movimentos é 2^n - 1.
1Relação de recorrênciaT(n) = 2T(n-1) + 1
2Solução fechadaT(n) = 2ⁿ - 1
3Complexidade assintóticaO(2ⁿ)
LEVEL · soulevel.com.br
Alternativa A — ✅ Correta ⟵ GABARITO
A alternativa expressa O(2^n) (a notação na questão aparece como "O(2n )", mas trata-se da complexidade exponencial). A cada chamada recursiva, o problema gera duas subinstâncias de tamanho n-1, resultando em 2^n - 1 movimentos no total.
Alternativa B — ❌ Incorreta
O(n) – complexidade linear. O algoritmo não é linear; o número de movimentos dobra aproximadamente a cada disco adicionado. Confunde-se com algoritmos que percorrem uma estrutura uma única vez (ex.: busca linear).
Alternativa C — ❌ Incorreta
O(n log n) – complexidade linearítmica. Típica de algoritmos de ordenação eficientes (merge sort, quicksort). Torre de Hanói não possui essa característica.
Alternativa D — ❌ Incorreta
O(n²) – complexidade quadrática. Comum em algoritmos como bubble sort. A Torre de Hanói é exponencial, muito mais custosa para n grandes.
Alternativa E — ❌ Incorreta
O(log n) – complexidade logarítmica. Característica de busca binária. Aqui o número de operações cresce rapidamente, não de forma logarítmica.
PEGA ESSA DICA!
Para problemas recursivos, monte a recorrência e resolva. Torre de Hanói é o exemplo clássico de complexidade exponencial. Grave a relação T(n) = 2T(n-1) + 1 → O(2^n). Ela aparece frequentemente em provas de concurso.
Conclusão: A complexidade do algoritmo da Torre de Hanói no pior caso é O(2^n), correspondente à alternativa A.