Análise de Complexidade - Fundamentos Flashcards
O que é análise de complexidade de algoritmos?
É o estudo de como o tempo de execução ou o uso de memória de um algoritmo cresce em função do tamanho de sua entrada.
O que é notação Big O?
A notação Big O descreve um limite superior da complexidade de um algoritmo à medida que o tamanho da entrada aumenta.
Um algoritmo que executa em tempo O(n²) é mais lento para entradas suficientemente grandes que um algoritmo que executa em tempo O(n). Verdadeiro ou falso? Justifique.
Falso. Pela definição da notação O, um algoritmo que sempre executa em tempo constante também é O(n²) e por consequência pode ser mais rápido que um algoritmo que executa em velocidade linear.
Um algoritmo que executa em tempo Θ(n²) é sempre mais lento que um algoritmo que executa em tempo Θ(n). Verdadeiro ou falso? Justifique.
Falso. Análise assintótica calcula a velocidade para valores grandes o suficiente para tornarem irrelevantes as constantes dos valores menores. Para entradas pequenas, um algoritmo que precisa de n² operações para ser executado é mais rápido que um algoritmo que precisa de 1000 * n operações.
Qual a vantagem de usar a notação Big O para medir o tempo de execução ao invés do tempo em segundos?
Ao usar a notação Big O, conseguimos medir o impacto do número de operações no algoritmo no seu tempo de execução enquanto o tempo de execução em segundos leva em conta aspectos como velocidade do computador.
Qual a vantagem de usar a notação Big O para medir a quantidade de operações de um programa ao invés de contar quantas operações são feitas?
A notação Big O permite que você compare o que acontece com a quantidade de operações quando o tamanho da entrada aumenta. Nesse aspecto, o número total de operações é irrelevante, o que importa é entender o que acontece com esse número quando a entrada dobra ou triplica.
Qual é o significado de O(1)?
O(1) significa que o tempo de execução ou espaço utilizado é constante, independente do tamanho da entrada.
Dê um exemplo de algoritmo com complexidade O(1).
Acesso direto a um elemento em uma lista, como array[i]; inserção de um elemento em uma pilha; remoção de um elemento em uma pilha; acesso a um elemento em uma tabela hash.
Qual é o significado de O(n)?
O(n) indica que o tempo de execução cresce no máximo linearmente com o tamanho da entrada.
Dê um exemplo de algoritmo com complexidade O(n).
Qualquer algoritmo que envolva percorrer todos os elementos em uma lista uma única vez.
O que significa O(n²)?
O(n²) indica que o tempo de execução cresce no máximo ao quadrado do tamanho da entrada.
Dê um exemplo de algoritmo com complexidade O(n²).
Métodos de ordenação simples (Bubble Sort; Insertion Sort; Selection Sort)
O que é notação Ômega (Ω)?
A notação Ômega descreve um limite inferior para o crescimento da complexidade de um algoritmo.
O que é notação Theta (Θ)?
A notação Ômega descreve um limite justo para o crescimento da complexidade de um algoritmo, indicando que ele nunca será muito melhor (nem pior) que aquele valor.
Qual é a complexidade de um algoritmo que dobra o número de operações para cada incremento na entrada?
O(2^n), exponencial.
O que significa O(log n)?
O(log n) significa que o tempo de execução cresce proporcionalmente ao logaritmo do tamanho da entrada.
Dê um exemplo de algoritmo com complexidade O(log n).
A busca binária em uma lista ordenada.
Qual é a complexidade de tempo de acessar um elemento por índice em uma lista?
a) O(n)
b) O(log n)
c) O(1)
d) O(n²)
c) O(1)
Qual é a complexidade de tempo do algoritmo de busca binária?
a) O(n)
b) O(log n)
c) O(1)
d) O(n²)
b) O (log n)
Se um algoritmo dobra o número de operações a cada incremento na entrada, sua complexidade é:
a) O(n²)
b) O(log n)
c) O(2^n)
d) O(n!)
c) O(2^n)
A complexidade de tempo para encontrar o maior elemento em uma lista não ordenada é:
a) O(n)
b) O(log n)
c) O(1)
d) O(n²)
a) O(n)
Qual é a complexidade de verificar se um número está presente em uma lista ordenada usando busca linear?
a) O(n)
b) O(log n)
c) O(1)
d) O(n²)
a) O(n)
Um algoritmo que sempre executa a mesma quantidade de passos, independentemente do tamanho da entrada, tem complexidade:
a) O(n)
b) O(log n)
c) O(1)
d) O(n²)
c) O(1)
O que acontece com a complexidade O(n log n) quando a entrada dobra?
a) Dobra
b) Aumenta em mais do que o dobro, mas menos que quatro vezes
c) Quadruplica
d) Não muda
b) Aumenta em mais do que o dobro, mas menos que quatro vezes
A complexidade de espaço de um algoritmo que usa recursão geralmente inclui:
a) O espaço usado pelos dados
b) O espaço para a pilha de chamadas recursivas
c) As variáveis globais
d) Todas as alternativas estão corretas
d) Todas as alternativas estão corretas
Um algoritmo com complexidadeO(n³) terá desempenho ruim para:
a) Entradas pequenas
b) Entradas médias
c) Entradas grandes
d) Nenhuma das opções acima
c) Entradas grandes
ual é a complexidade de criar uma cópia de uma lista com n elementos?
a) O(n)
b) O(log n)
c) O(1)
d) O(n²)
a) O(n)
Qual é a complexidade de encontrar o maior valor presente em duas listas de tamanhos n e m?
a) O(1)
b) O(n+m)
c) O(n²)
d) O(log n)
b) O(n + m)
Qual algoritmo de busca tem desempenho O(1) no melhor caso?
a) Busca linear
b) Busca binária
c) Busca em tabela hash
d) Todas as alternativas estão corretas
d) Todas as alternativas estão corretas
