Lista de exercícios de Algoritmos e complexidade com respostas

Quanto é log₂ 1024?

1. A12
2. B32
3. C10
4. D512

Qual é o O grande de 3n² + 5n + 2?

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

Um laço começa com i = 1 e dobra i a cada iteração até i > n. Quantas iterações ele executa?

1. ACerca de n²
2. BCerca de log₂ n
3. CCerca de n
4. DCerca de n / 2

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³)

É correto dizer que um algoritmo O(n²) também é O(n³)?

1. ANão, porque o O grande deve sempre dar a taxa de crescimento exata da função
2. BSim, mas só se n for menor que 100
3. CSim, porque o O grande é um limite superior e n² não cresce mais rápido que n³
4. DNão, porque n³ é menor que n² para n grande

Qual é a complexidade de tempo amortizada de adicionar ao final de um array dinâmico que dobra sua capacidade quando fica cheio?

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

Qual afirmação sobre P e NP está correta?

1. ATodo problema em P também está em NP
2. BFoi provado que P ≠ NP
3. CSoluções de problemas NP não podem ser verificadas rapidamente
4. DNP significa "não polinomial"

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É indecidível
2. BÉ NP-difícil
3. CPode ser resolvido pelo algoritmo de Dijkstra com os pesos negados
4. DÉ sempre solúvel em O(V + E)