Lista de exercícios de Algoritmos e complexidade com respostas

O que descreve o tempo de execução de um algoritmo no pior caso?

1. AO tempo que leva com a menor entrada
2. BO tempo que leva num computador lento
3. CO tempo esperado que leva com uma entrada aleatória de tamanho n
4. DO tempo máximo que ele leva entre todas as entradas de tamanho n

Um problema costuma ser chamado de tratável se:

1. ASó pode ser resolvido testando todas as possibilidades
2. BNão tem solução
3. CPode ser resolvido em tempo polinomial
4. DPode ser resolvido em tempo constante

Acessar um elemento de um array pelo índice leva:

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

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. AO merge sort não tem estrutura recursiva
2. BSeus subproblemas não se sobrepõem, então não há nada para reaproveitar
3. CA programação dinâmica só funciona em problemas de grafos, não em vetores
4. DO merge sort já é O(n)

A complexidade de tempo do Fibonacci recursivo ingênuo (fib(n) = fib(n−1) + fib(n−2)) é:

1. AConstante
2. BExponencial
3. CLogarítmica
4. DLinear

Qual é a complexidade de tempo de: for i = 1 to n: for (j = i; j ≤ n; j = j + i) faça trabalho O(1)?

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

O problema da mochila 0/1 resolvido com programação dinâmica leva tempo O(nW). Por que isso é chamado de pseudopolinomial?

1. APorque n é sempre pequeno
2. BW é um número, então o tempo é exponencial no número de bits usados para escrever W
3. CPorque o algoritmo é aleatorizado e seu tempo de execução varia a cada entrada
4. DPorque só funciona para W = 0