Lista de exercícios de Algoritmos e complexidade com respostas

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

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

O que significa uma operação rodar em tempo O(1)?

1. ASempre leva exatamente um segundo
2. BProcessa exatamente um elemento por segundo de tempo de execução
3. CSeu tempo de execução não cresce com o tamanho da entrada
4. DSó pode ser executada uma vez

Um algoritmo O(n²) leva 1 segundo para n = 1000. Quanto tempo leva, aproximadamente, para n = 2000?

1. A4 segundos
2. B8 segundos
3. C2 segundos
4. D1 segundo

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

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

Por que a programação dinâmica não traz ganho real de velocidade para o merge sort?

1. AA programação dinâmica só funciona em problemas de grafos, não em vetores
2. BO merge sort não tem estrutura recursiva
3. CO merge sort já é O(n)
4. DSeus subproblemas não se sobrepõem, então não há nada para reaproveitar

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

1. ASim, mas só se n for menor que 100
2. BNão, porque n³ é menor que n² para n grande
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³

Qual limite está correto para log(n!)?

1. AΘ(n)
2. BΘ(n²)
3. CΘ(n log n)
4. DΘ(log n)

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)