Questão de Tecnologia da Informação · FGV CVM 2024 (nº 28)

A complexidade computacional mede como o tempo de execução (ou o uso de memória) de um algoritmo cresce à medida que o tamanho da entrada (n) aumenta. Para algoritmos recursivos, como a Torre de Hanói, analisamos o número de operações (como movimentos ou chamadas de função) em função do número de discos (n).

O algoritmo da Torre de Hanói segue uma relação de recorrência. Se $T(n)$ é o número de movimentos para $n$ discos:

• Para $n=1$, há 1 movimento: $T(1) = 1$.
• Para $n > 1$, o problema é dividido em três passos:
  1. Mover $n-1$ discos da origem para o pino auxiliar: $T(n-1)$ movimentos.
  2. Mover o disco $n$ (o maior) da origem para o destino: 1 movimento.
  3. Mover $n-1$ discos do pino auxiliar para o destino: $T(n-1)$ movimentos.
     Isso nos dá a relação: $T(n) = T(n-1) + 1 + T(n-1) \implies T(n) = 2T(n-1) + 1$.

Resolvendo essa recorrência:
$T(n) = 2T(n-1) + 1$
$T(n) = 2(2T(n-2) + 1) + 1 = 4T(n-2) + 2 + 1$
$T(n) = 4(2T(n-3) + 1) + 3 = 8T(n-3) + 4 + 3$
Generalizando, $T(n) = 2^k T(n-k) + (2^k - 1)$.
Para $k = n-1$: $T(n) = 2^{n-1} T(1) + (2^{n-1} - 1)$.
Como $T(1) = 1$: $T(n) = 2^{n-1} \times 1 + 2^{n-1} - 1 = 2 \times 2^{n-1} - 1 = 2^n - 1$.

Portanto, o número de movimentos (e, consequentemente, de operações) é $2^n - 1$. Em notação Big O, que foca na ordem de crescimento, a complexidade é $O(2^n)$.

(A) Correta: A complexidade do algoritmo da Torre de Hanói é exponencial, dada pelo número de movimentos $2^n - 1$. Em notação Big O, isso é $O(2^n)$, indicando um crescimento exponencial. A alternativa $O(2n)$ formalmente representa um crescimento linear, equivalente a $O(n)$. A armadilha aqui é confundir a base da exponenciação (o '2' de $2^n$) com um coeficiente linear (o '2' de $2n$), ou talvez somar o número de chamadas recursivas (duas) com a profundidade da recursão (n). No entanto, seguindo o gabarito oficial, esta é a alternativa a ser considerada como correta, apesar da notação $O(2n)$ ser usualmente associada a um crescimento linear.
(B) Incorreta: $O(n)$ indica um crescimento linear, muito mais lento do que o crescimento exponencial real do algoritmo da Torre de Hanói.
(C) Incorreta: $O(n \log n)$ é uma complexidade comum em algoritmos de ordenação eficientes, mas não se aplica ao problema da Torre de Hanói, que tem um crescimento muito mais rápido.
(D) Incorreta: $O(n^2)$ indica um crescimento quadrático, que é mais lento que o crescimento exponencial do algoritmo da Torre de Hanói.
(E) Incorreta: $O(\log n)$ indica um crescimento logarítmico, que é extremamente eficiente e não corresponde à complexidade do algoritmo da Torre de Hanói.