Big O

Text Material Preview

Big O 
O que a notacao Big O (O grande) descreve?
a) O melhor caso de execucao de um algoritmo
b) O tempo medio de execucao de um algoritmo
c) O pior caso de execucao de um algoritmo
d) O comportamento do algoritmo com entradas pequenas
Resposta correta: c) A notacao Big O e usada para descrever o pior caso de execucao de um
algoritmo, ou seja, o tempo maximo que o algoritmo pode levar para executar uma tarefa.
Qual e a principal razao para utilizar a notacao Big O ao analisar algoritmos?
a) Para medir a eficiencia de um algoritmo em termos de tempo e espaco
b) Para calcular o numero de linhas de codigo no algoritmo
c) Para determinar a quantidade de memoria necessaria para rodar o algoritmo
d) Para medir a compatibilidade do algoritmo com diferentes sistemas operacionais
Resposta correta: a) A notacao Big O e usada para medir a eficiencia de um algoritmo,
descrevendo como o tempo de execucao (ou o uso de memoria) cresce conforme o tamanho da
entrada aumenta.
Qual das alternativas a seguir representa um exemplo de um algoritmo com complexidade O(n)?
a) Algoritmo de ordenacao por selecao
b) Algoritmo de busca binaria
c) Algoritmo de busca linear
d) Algoritmo de ordenacao merge sort
Resposta correta: c) A busca linear tem complexidade O(n), o que significa que, no pior caso, o
algoritmo verifica todos os elementos da lista.
Como a notacao Big O ajuda a comparar algoritmos?
a) Ela permite comparar o tempo de execucao de algoritmos com entradas pequenas
b) Ela descreve apenas a eficiencia de algoritmos em termos de uso de memoria
c) Ela ajuda a comparar como o tempo de execucao de diferentes algoritmos cresce a medida que
o tamanho da entrada aumenta
d) Ela calcula o numero de passos que um algoritmo precisa para encontrar uma solucao
Resposta correta: c) A notacao Big O ajuda a comparar como o tempo de execucao de diferentes
algoritmos cresce a medida que o tamanho da entrada aumenta, permitindo uma analise mais
precisa da eficiencia de cada algoritmo.
Qual e a complexidade assintotica de um algoritmo de busca binaria em uma lista ordenada?
a) O(n)
b) O(n log n)
c) O(log n)
d) O(n2)
Resposta correta: c) A busca binaria possui complexidade O(log n), ja que a cada iteracao o
numero de elementos que precisa ser considerado e reduzido pela metade.
Quando dizemos que um algoritmo tem complexidade O(1), o que isso significa?
a) O tempo de execucao cresce linearmente com o tamanho da entrada
b) O tempo de execucao cresce logaritmicamente com o tamanho da entrada
c) O tempo de execucao e constante, independentemente do tamanho da entrada
d) O tempo de execucao cresce exponencialmente com o tamanho da entrada
Resposta correta: c) A complexidade O(1) significa que o tempo de execucao do algoritmo e
constante, nao importa o tamanho da entrada.
Qual e a complexidade assintotica do algoritmo de ordenacao Bubble Sort?
a) O(n log n)
b) O(n2)
c) O(n)
d) O(log n)
Resposta correta: b) O algoritmo Bubble Sort tem uma complexidade O(n2) no pior caso, pois ele
realiza comparacoes e trocas em um numero quadratico de iteracoes.
Qual e a principal desvantagem de algoritmos com complexidade O(n2)?
a) Eles sao eficientes para entradas muito pequenas
b) Eles nao podem ser implementados em linguagens de programacao populares
c) Eles podem ser lentos para entradas grandes, pois o tempo de execucao cresce quadradamente
d) Eles sao otimos para lidar com entradas muito grandes
Resposta correta: c) Algoritmos com complexidade O(n2) podem ser lentos quando o tamanho da
entrada e grande, pois o tempo de execucao cresce quadradamente.
O que caracteriza a complexidade O(n log n)?
a) O tempo de execucao aumenta linearmente com o tamanho da entrada
b) O tempo de execucao cresce logaritmicamente com o tamanho da entrada
c) O tempo de execucao cresce exponencialmente com o tamanho da entrada
d) O tempo de execucao cresce linearmente e logaritmicamente com o tamanho da entrada
Resposta correta: d) A complexidade O(n log n) descreve um crescimento que e linear combinado
com um fator logaritmico, o que a torna eficiente para algoritmos como Merge Sort e Quick Sort.
Qual e a complexidade assintotica do algoritmo Quick Sort?
a) O(n log n)
b) O(n2)
c) O(n)
d) O(log n)
Resposta correta: a) O Quick Sort tem uma complexidade O(n log n) no caso medio, mas pode
chegar a O(n2) no pior caso, dependendo da escolha do pivo.
Quando um algoritmo possui complexidade O(n log n), qual e o seu comportamento?
a) O tempo de execucao aumenta linearmente com o tamanho da entrada
b) O tempo de execucao aumenta exponencialmente com o tamanho da entrada
c) O tempo de execucao cresce linearmente e logaritmicamente com o tamanho da entrada
d) O tempo de execucao cresce quadradamente com o tamanho da entrada
Resposta correta: c) A complexidade O(n log n) implica que o tempo de execucao cresce com uma
combinacao de um fator linear e logaritmico a medida que o tamanho da entrada aumenta.
Qual e a complexidade do algoritmo de ordenacao Insertion Sort no pior caso?
a) O(n log n)
b) O(n2)
c) O(n)
d) O(log n)
Resposta correta: b) O algoritmo Insertion Sort tem complexidade O(n2) no pior caso, quando os
elementos estao em ordem inversa e o algoritmo precisa realizar o maior numero possivel de
comparacoes e deslocamentos.
Qual e a complexidade de um algoritmo que realiza uma operacao constante em cada iteracao de
um laco que itera n vezes?
a) O(n)
b) O(log n)
c) O(1)
d) O(n2)
Resposta correta: a) Se um algoritmo realiza uma operacao constante em cada uma das n
iteracoes de um laco, sua complexidade e O(n).
Como a notacao Big O pode ser usada para descrever o comportamento de algoritmos em
diferentes cenarios de entrada?
a) Descreve apenas o comportamento em entradas pequenas
b) Descreve o pior caso, o melhor caso e o caso medio
c) Calcula apenas o tempo medio de execucao
d) Nao pode ser usada para descrever o comportamento em diferentes cenarios
Resposta correta: b) A notacao Big O e comumente usada para descrever o pior caso de um
algoritmo, mas tambem pode ser aplicada para descrever o melhor caso e o caso medio,
dependendo da situacao.
Qual e a diferenca entre O(n log n) e O(n2)?
a) O(n log n) e mais eficiente para entradas grandes, enquanto O(n2) e mais eficiente para
entradas pequenas
b) O(n2) cresce mais lentamente que O(n log n)
c) O(n log n) cresce mais rapidamente do que O(n2)
d) Nao ha diferenca, ambas sao equivalentes
Resposta correta: a) O(n log n) tende a ser mais eficiente para entradas grandes, enquanto O(n2)
pode se tornar muito lento a medida que o tamanho da entrada aumenta.
Em que tipo de algoritmos encontramos a complexidade O(n2)?
a) Algoritmos de busca binaria
b) Algoritmos de ordenacao eficientes, como Quick Sort
c) Algoritmos simples de ordenacao, como Bubble Sort e Selection Sort
d) Algoritmos de busca em arvores balanceadas
Resposta correta: c) Algoritmos simples de ordenacao, como Bubble Sort e Selection Sort,
possuem complexidade O(n2), o que os torna menos eficientes para grandes entradas.
Qual e a complexidade de um algoritmo com uma operacao constante que e executada para cada
elemento de uma lista de tamanho n?
a) O(n)
b) O(n2)
c) O(log n)
d) O(1)
Resposta correta: a) Se um algoritmo realiza uma operacao constante para cada elemento de uma
lista de tamanho n, sua complexidade sera O(n).
Como a complexidade O(n2) afeta o desempenho de um algoritmo em entradas grandes?
a) O desempenho nao e afetado, o algoritmo permanece eficiente
b) O desempenho piora significativamente a medida que o tamanho da entrada cresce
c) O algoritmo se torna mais rapido a medida que o tamanho da entrada aumenta
d) O desempenho do algoritmo e sempre constante
Resposta correta: b) Algoritmos com complexidade O(n2) tendem a se tornar mais lentos a medida
que o tamanho da entrada cresce, devido