GabaritoA — O(1)
Gabarito: letra A (O(1)). Quando a senha tem comprimento fixo, independentemente do seu valor específico, o algoritmo de hash executa um número constante de operações para gerar o resumo. A complexidade temporal é constante – O(1) – e não depende do tamanho da entrada (que é invariável).
A questão testa a compreensão de que a análise de complexidade considera o tamanho da entrada (n). Se a entrada tem tamanho fixo, o tempo de execução não varia com n, logo a ordem é constante.
Para uma senha de comprimento fixo, o hash criptográfico aplica uma sequência predefinida de operações (expansão, mistura, compressão) que não varia com o conteúdo da senha. Portanto, a complexidade temporal é {{O(1)}} – tempo constante.
O(log n) é a complexidade típica de algoritmos que dividem o problema pela metade a cada passo (busca binária). O hash em entrada fixa não possui crescimento logarítmico; ele é constante.
O(n) seria a complexidade se o tempo crescesse linearmente com o tamanho da entrada. Como a entrada é fixa, o tempo é constante, não linear.
O(n log n) é comum em algoritmos de ordenação eficientes (merge sort, quicksort). Não se aplica ao processamento de hash de tamanho fixo.
O(n²) é característico de algoritmos com laços aninhados que percorrem a entrada. No hash de entrada fixa, não há dependência quadrática.
Gabarito: letra A.
Link permanente: /questoes/fg131885