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 num computador lento
2. BO tempo máximo que ele leva entre todas as entradas de tamanho n
3. CO tempo que leva com a menor entrada
4. DO tempo esperado que leva com uma entrada aleatória de tamanho n

Qual algoritmo de ordenação troca repetidamente elementos adjacentes que estão na ordem errada?

1. AHeap sort
2. BQuicksort
3. CMerge sort (ordenação por intercalação)
4. DBubble sort (ordenação por bolha)

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

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

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

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

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

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²)
2. BO(n log n)
3. CO(n)
4. DO(log 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 só funciona para W = 0
2. BPorque n é sempre pequeno
3. CW é um número, então o tempo é exponencial no número de bits usados para escrever W
4. DPorque o algoritmo é aleatorizado e seu tempo de execução varia a cada entrada

Para qual variante da mochila a regra gulosa "pegar os itens em ordem de valor por peso" sempre dá uma resposta ótima?

1. AAs duas variantes
2. BA mochila fracionária, em que os itens podem ser divididos
3. CNenhuma das variantes
4. DA mochila 0/1, em que os itens devem ser sempre levados inteiros