Em ciências da computação, quando desejamos identificar o es...
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 algorlbno 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.
lI. 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).
IlI. 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).
- Gabarito Comentado (1)
- Aulas (1)
- Comentários (0)
- Estatísticas
- Cadernos
- Criar anotações
- Notificar Erro
Gabarito comentado
Confira o gabarito comentado por um dos nossos professores
Alternativa correta: E - Todas as afirmativas estão corretas.
Vamos agora entender cada uma das afirmativas e justificar por que todas elas estão corretas.
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.
Esta afirmativa está correta. A notação Big O é amplamente utilizada para descrever a complexidade de algoritmos, mas não é a única. A Big Omega (Ω) é utilizada para descrever o limite inferior (o melhor caso) da complexidade de um algoritmo, enquanto a Big Theta (Θ) descreve a complexidade assintótica exata (quando o limite superior e inferior são iguais).
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 da instância de entrada (n).
Esta afirmativa também está correta. A notação Big O nos permite comparar a taxa de crescimento das funções. Um algoritmo com complexidade O(n2) cresce quadraticamente, enquanto um algoritmo O(log n) cresce logaritmicamente. Portanto, à medida que n aumenta, o tempo de execução do algoritmo O(n2) aumenta muito mais rapidamente do que o do algoritmo O(log n).
III. Algoritmos de complexidade constante são aqueles cujo 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 O(1).
Esta afirmativa está correta. Complexidade constante (O(1)) significa que o tempo de execução do algoritmo não depende do tamanho da entrada. Não importa se a entrada tem 10 itens ou 1.000.000 de itens, o tempo de execução será o mesmo. Um exemplo clássico de complexidade O(1) é o acesso a um elemento específico em um array (por índice).
Conclusão: Todas as afirmativas I, II e III estão corretas, portanto, a alternativa correta é a alternativa E.
Gostou do comentário? Deixe sua avaliação aqui embaixo!
Clique para visualizar este gabarito
Visualize o gabarito desta questão clicando no botão abaixo
Conheça nossos planos