Lista de exercícios de Algoritmos e complexidade com respostas

O que é memoização?

1. AEscrever comentários ao lado de cada linha de código
2. BArmazenar os resultados de chamadas de função para que chamadas repetidas sejam respondidas da memória
3. CConverter automaticamente a recursão em um laço equivalente, de modo que não seja preciso pilha de chamadas
4. DLiberar memória depois que uma função retorna

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

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

O que a busca binária exige da sua entrada?

1. AO tamanho do array deve ser uma potência de dois
2. BO array deve conter só números positivos
3. CO array não pode ter mais de 1000 elementos
4. DO array deve estar ordenado

Por que muitas rotinas de ordenação de bibliotecas passam para o insertion sort em subarrays muito pequenos?

1. AO insertion sort tem pouco overhead e é rápido com entradas pequenas ou quase ordenadas
2. BO insertion sort é O(n log n) no pior caso
3. CAlgoritmos recursivos não conseguem lidar com arrays de menos de 10 elementos
4. DO insertion sort usa menos memória que qualquer outro algoritmo de ordenação em entradas grandes

Num array ordenado, você procura dois elementos cuja soma seja um alvo movendo um ponteiro de cada extremidade para dentro. Qual é a complexidade de tempo?

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

O que a análise amortizada mede?

1. AO custo de um algoritmo com a melhor entrada
2. BO custo médio por operação ao longo de uma sequência de operações de pior caso
3. CO custo da operação individual mais cara em qualquer ponto da sequência
4. DO custo esperado sobre entradas aleatórias

Um problema é NP-completo se ele:

1. AEstá em NP e todo problema NP se reduz a ele em tempo polinomial
2. BEstá fora de NP, mas é mais difícil que todos os problemas NP, como o problema da parada
3. CPode ser resolvido em tempo polinomial
4. DÉ impossível de resolver

Qual é o tempo de execução do algoritmo de Dijkstra com um heap binário num grafo com V vértices e E arestas?

1. AO((V + E) log V)
2. BO(V × E)
3. CO(V³)
4. DO(V + E)