Lista de exercícios de Algoritmos e complexidade com respostas

Qual classe de complexidade cresce mais rápido para n grande?

1. AO(n³)
2. BO(n²)
3. CO(2ⁿ)
4. DO(n log n)

Um problema costuma ser chamado de tratável se:

1. ANão tem solução
2. BPode ser resolvido em tempo polinomial
3. CPode ser resolvido em tempo constante
4. DSó pode ser resolvido testando todas as possibilidades

O que é um algoritmo?

1. AUma linguagem de programação criada para escrever fórmulas matemáticas
2. BUma estrutura de dados que armazena números
3. CQualquer programa de computador com interface gráfica
4. DUma sequência finita de passos bem definidos que resolve um problema

Qual é a complexidade de tempo de multiplicar duas matrizes n × n com o laço triplo padrão?

1. AO(n² log n)
2. BO(n)
3. CO(n³)
4. DO(n²)

Quanto espaço de pilha usa uma função fatorial recursiva simples fact(n) = n × fact(n − 1)?

1. AO(n)
2. BO(log n)
3. CO(n²)
4. DO(1)

No problema de seleção de atividades, qual regra gulosa sempre dá o número máximo de atividades sem sobreposição?

1. AEscolher a atividade que começa mais cedo
2. BEscolher a atividade que termina mais cedo e repetir com as compatíveis
3. CEscolher primeiro a atividade com menos sobreposições e repetir com as compatíveis
4. DEscolher primeiro a atividade mais curta

Caminhos simples mínimos podem ser encontrados em tempo polinomial. O que se sabe sobre encontrar o caminho simples mais longo entre dois vértices num grafo geral?

1. AÉ NP-difícil
2. BÉ sempre solúvel em O(V + E)
3. CPode ser resolvido pelo algoritmo de Dijkstra com os pesos negados
4. DÉ indecidível

Como n! e 2ⁿ se comparam para n grande?

1. An! cresce mais rápido que 2ⁿ
2. BCrescem no mesmo ritmo
3. C2ⁿ cresce mais rápido que n!
4. Dn! é O(n²)