Questão de Algoritmos e Estrutura de Dados — Algoritmos — INSTITUTO AOCP 2025
Algoritmos e Estrutura de Dados›Algoritmos
Código
qg541065
Banca
INSTITUTO AOCP
Órgão
Prefeitura de Joinville - SC
Ano
2025
Nível
Superior
Cargo
Analista de Tecnologia da Informação
A complexidade de algoritmos é uma métrica fundamental para avaliar a eficiência de programas, permitindo estimar o tempo de execução e o consumo de recursos em função do tamanho da entrada. Diversas notações são utilizadas para descrever o comportamento de algoritmos em diferentes cenários, como melhor caso, pior caso e casos médios, assim como a complexidade de tempo, que indica o crescimento do tempo de execução conforme a quantidade de dados aumenta. Sobre complexidade de algoritmos, informe se é verdadeiro (V) ou falso (F) o que se afirma a seguir e assinale a alternativa com a sequência correta.( ) A notação empregada para representar o melhor caso de um determinado algoritmo é Ω (Omega).( ) A notação empregada para representar o pior caso em casos gerais de um determinado algoritmo é Θ (Theta).( ) O(1) – tempo de execução constante, que não varia conforme o tamanho da entrada do algoritmo.( ) Quanto à complexidade de tempo, O(n) – tempo quadrático, cresce proporcionalmente ao tamanho da entrada.
AV – F – V – F.
BF – V – V – F.
CF – V – F – V.
DV – V – F – F.
EV – F – F – V.
Revelar gabarito e comentário▾
GabaritoA — V – F – V – F.
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”.
Complexidade de Algoritmos: Notações Assintóticas
Gabarito: alternativa A — sequência V – F – V – F. A notação Ω (Omega) representa o melhor caso (limitante inferior); O (Big O) representa o pior caso (limitante superior); e Θ (Theta) representa o caso justo (quando os limitantes coincidem). O(1) é tempo constante, e O(n) é linear, não quadrático.
A banca cobra o conhecimento das três principais notações assintóticas. Observe a tabela-resumo:
Notação
Nome
Significado
Cenário típico
O (Big O)
Limitante superior
Crescimento não excede f(n)
Pior caso
Ω (Omega)
Limitante inferior
Crescimento não é menor que f(n)
Melhor caso
Θ (Theta)
Limitante justo
Crescimento é exatamente f(n)
Caso médio / tight bound
1ª afirmativa — ✅ Verdadeira
"A notação empregada para representar o melhor caso de um determinado algoritmo é Ω (Omega)."
Correta. A notação Ω (ômega) descreve o limitante inferior assintótico, ou seja, a menor taxa de crescimento que o algoritmo pode apresentar. Exatamente o que se espera do melhor caso.
2ª afirmativa — ❌ Falsa
"A notação empregada para representar o pior caso em casos gerais de um determinado algoritmo é Θ (Theta)."
Falsa. O pior caso é expresso pela notação O (Big O), que fornece o limitante superior. A notação Θ (Theta) é usada quando os limitantes superior e inferior coincidem, indicando que o algoritmo tem o mesmo comportamento assintótico em todos os casos (caso justo). Portanto, a afirmação troca o papel do O e do Θ.
NÃO CAIA NESSA!
A banca inverte a função do Θ, fazendo-o parecer a notação padrão para o pior caso. Na verdade, Θ é usada para casos justos (onde melhor e pior caso são iguais), e O é a notação correta para o pior caso. Não caia nessa troca!
3ª afirmativa — ✅ Verdadeira
"O(1) – tempo de execução constante, que não varia conforme o tamanho da entrada do algoritmo."
Correta. O(1) é a notação que representa complexidade constante: o tempo de execução não depende do tamanho da entrada (n). Por exemplo, acessar um elemento de um array por índice é O(1).
4ª afirmativa — ❌ Falsa
"Quanto à complexidade de tempo, O(n) – tempo quadrático, cresce proporcionalmente ao tamanho da entrada."
Falsa. O(n) é complexidade linear, não quadrática. O tempo quadrático é representado por O(n²). A afirmação confunde a ordem de crescimento: O(n) cresce proporcionalmente a (n); O(n²) cresce com o quadrado de (n).
Conclusão: As afirmativas verdadeiras são a 1ª e a 3ª; a 2ª e a 4ª são falsas. Portanto, a sequência correta é V – F – V – F, que corresponde à alternativa A.
PEGA ESSA DICA!
Memorize o quadro: O = maior (pior), Ω = menor (melhor), Θ = igual (caso justo). Para ordens de crescimento: O(1) constante, O(n) linear, O(n²) quadrático. Esses são os conceitos mais cobrados em concursos sobre complexidade.