Questão FC266072
Em ciências da computação, quando desejamos identificar o esforço necessário para um algoritmo executar uma determinada tarefa, buscamos medir qual a complexidade daquele algoritmo
Algoritmos e Lógica de Programação
IDECAN · 2022
Em ciências da computação, quando desejamos identificar o esforço necessário para um algoritmo executar uma determinada tarefa, buscamos medir qual a complexidade daquele algoritmo. Para realizar tal medição buscamos identificar uma função que, com base no tamanho da Instância de entrada N, consiga determinar o esforço que o algoritmo realizará.
A respeito dos conceitos que envolvem o estudo da complexidade de algoritmos, analise as afirmativas abaixo e marque alternativa correta.
I. Big O é a notação mais conhecida para a indicação da complexidade de algoritmos. Além dela, existem outras notações, como por exemplo a Big Omega e Big Theta.
II. Um algoritmo com notação Big O igual a O(n2) tem maior complexidade que um algoritmo com notação Big O igual a O(log n). Dito de outra forma, o tempo de processamento do primeiro cresce mais rápido que o tempo de processamento do segundo, à medida que aumentamos o tamanho instância de entrada (n).
III. Algoritmos de complexidade constante são aqueles cujo o tempo de processamento não aumenta de acordo com o tamanho da instância de entrada. Em Big O algoritmos com esse tipo de complexidade são representados pela notação 0(1).
- Apenas as afirmativas I e III estão corretas.
- Apenas a afirmativa II está correta.
- Apenas as afirmativas II e III estão corretas.
- Apenas a afirmativa III está correta.
- Todas as afirmativas estão corretas.
Mostrar resposta e comentário
Gabarito
Errado
Comentário do professor
A alternativa indica que todas as afirmativas estão corretas. Explica-se a seguir o porquê.
Big O é a notação mais usada para descrever o crescimento assintótico superior do tempo/espaco de um algoritmo. Há também Big Omega (limite inferior) e Big Theta (limite apertado), que complementam a análise assintótica.
Sobre crescimento: uma função quadrática \(n^2\) cresce muito mais rápido que uma logarítmica \(\log n\). Formalmente, \(\lim_{n\to\infty}\frac{\log n}{n^2}=0\), portanto \(O(n^2)\) domina \(O(\log n)\).
Complexidade constante são algoritmos cujo tempo não depende do tamanho da entrada; representam-se por \(O(1)\) — por exemplo, acesso direto a um elemento por índice.
Conteúdo do catálogo FC Concursos · Atualizado em