Lista de exercícios de Algoritmos e complexidade com respostas

O que significa f(n) = Θ(g(n))?

1. Af cresce no mesmo ritmo que g, limitada por cima e por baixo por múltiplos constantes de g
2. Bf cresce estritamente mais devagar que g
3. Cf é sempre menor que g para todo n, então g a limita por cima, mas nunca por baixo
4. Df cresce estritamente mais rápido que g

Um laço começa com i = 1 e dobra i a cada iteração até i > n. Quantas iterações ele executa?

1. ACerca de n²
2. BCerca de log₂ n
3. CCerca de n / 2
4. DCerca de n

O tempo de execução de um algoritmo é O(n). Como se chama esse crescimento?

1. ALogarítmico
2. BQuadrático
3. CLinear
4. DConstante

Aproximadamente quantas comparações a busca binária precisa no pior caso num array ordenado de 1,000,000 de elementos?

1. ACerca de 500,000
2. BCerca de 20
3. CCerca de 1,000
4. DCerca de 100

Qual é a complexidade de tempo do quicksort no pior caso?

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

Qual é a complexidade de tempo de: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

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

O insertion sort roda em O(n) com entrada ordenada. Isso contradiz o limite inferior Ω(n log n) da ordenação por comparação?

1. ASim, portanto o limite inferior está errado
2. BSim, mas só para arrays com menos de 100 elementos
3. CNão, o limite inferior vale para o pior caso entre todas as entradas, não para cada entrada
4. DNão, porque o insertion sort não é uma ordenação por comparação

O problema da parada mostra que:

1. ALaços devem ser evitados
2. BAlguns programas rodam mais rápido em computadores mais rápidos, então a parada depende do hardware
3. CNenhum algoritmo consegue decidir, para todo programa e toda entrada, se o programa para
4. DTodo programa acaba parando