Quiz de Complexidade de Algoritmos

Qual notação assintótica descreve um algoritmo cujo tempo de execução permanece constante, independentemente do tamanho da entrada?

• O(1)

• O(n)

• O(n^2)

• O(log n)

Em notação Big O, qual classe de complexidade indica que o tempo de execução de um algoritmo é independente do tamanho da entrada?

• Constante

• Quadrática

• Logarítmica

• Linear

Um sistema de recomendação de filmes utiliza um algoritmo que compara as preferências de cada usuário com as de todos os outros para encontrar usuários similares e, assim, sugerir filmes. Se o algoritmo comparar cada usuário com todos os outros, qual das seguintes notações Big O melhor descreve a complexidade de tempo desse processo em relação ao número de usuários (n)?

• O(n log n)

• O(log n)

• O(n^2)

• O(n)

Em um projeto de análise de dados genômicos, você se depara com um algoritmo de alinhamento de sequências com complexidade O(2^n), que inviabiliza a análise de grandes genomas. Qual das seguintes estratégias seria mais eficaz para otimizar este algoritmo, visando reduzir a complexidade para um nível mais gerenciável?

• Paralelizar o algoritmo para distribuir a carga de trabalho entre múltiplos processadores e acelerar a execução.

• Implementar programação dinâmica para evitar recálculo de subproblemas e reduzir a complexidade para um nível polinomial.

• Aumentar a capacidade da memória RAM para permitir o processamento de conjuntos de dados maiores sem interrupções.

• Otimizar o uso de cache para reduzir o tempo de acesso aos dados frequentemente utilizados.

Em análise de algoritmos, a complexidade exponencial representa um desafio significativo devido ao seu rápido crescimento. Qual das seguintes situações ilustra melhor um cenário onde a complexidade de um algoritmo é classificada como exponencial?

• Simulação de todas as possíveis combinações em um problema de otimização combinatória.

• Impressão de cada elemento de um array.

• Busca binária em uma lista ordenada.

• Cálculo da média de um conjunto de números.

Em qual dos cenários a seguir a notação Big O pode ser menos precisa ao comparar dois algoritmos em um caso específico?

• Quando se analisa a complexidade de algoritmos recursivos, onde a profundidade da recursão é alta.

• Quando os algoritmos são executados em hardware significativamente diferentes, com um sendo executado em um sistema de alto desempenho e outro em um sistema de baixa capacidade.

• Quando os algoritmos são implementados em diferentes linguagens de programação, uma compilada e outra interpretada.

• Quando os tamanhos de entrada são consistentemente pequenos, e as constantes de tempo de execução se tornam fatores dominantes.

Questão 7. Em suas próprias palavras, explique por que a análise de complexidade, utilizando a notação Big O, é considerada uma ferramenta essencial para um programador ou cientista da computação no desenvolvimento de software, mesmo antes de começar a escrever o código. Inclua um exemplo prático de como essa análise pode influenciar as decisões de design de um algoritmo.