Lista de exercícios de Algoritmos e complexidade com respostas

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

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

A complexidade de espaço mede:

1. AO tamanho físico do computador
2. BO espaço em disco do arquivo do programa depois de compilado
3. CA quantidade de memória que um algoritmo precisa à medida que a entrada cresce
4. DO número de linhas de código

Qual é a complexidade de tempo da busca binária em um array ordenado?

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

Qual é o tempo de execução do radix sort LSD para n inteiros com d dígitos na base k?

1. AO(n²)
2. BO(n log n)
3. CO(d(n + k))
4. DO(dn log k)

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

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

A programação dinâmica é útil quando um problema tem:

1. AUm único laço
2. BNenhum subproblema, de modo que pode ser resolvido em um único passo
3. CSubproblemas sobrepostos e subestrutura ótima
4. DApenas entradas aleatórias

Quais duas coisas precisam ser mostradas para provar que um problema de decisão X é NP-completo?

1. AX está em NP, e um problema NP-completo conhecido se reduz a X em tempo polinomial
2. BX se reduz a um problema em P, e X está em NP
3. CX não tem algoritmo polinomial, e X é decidível
4. DX está em P, e X se reduz ao SAT

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