Complexidade de Algoritmos

A complexidade de algoritmos é um tópico dentro da ciência da computação que estuda o quanto um algoritmo é “difícil” de ser executado. A análise envolve o quanto de “esforço” o computador terá de fazer para executar um código. Pode parecer inofensivo, mas encadear 2 ou 3 “for” podem ser um problema grande! Nos exercícios a seguir você poderá treinar suas habilidades de análise. Mas cuidado, você precisa ter estudado um pouco sobre esse assunto antes, pois existem termos e teorias muito específicas abordadas nos exercícios.

Quer saber mais sobre esse tópico? veja um ótimo artigo de introdução

1 – Um algoritmo tem complexidade O(3m³ + 2mn² + n² + 10m + m²). Uma maneira simplificada de representar a complexidade desse algoritmo é:
A) O(m³ + mn²).
B) O(m³).
C) O(m²).
D) O(mn²).
E) O(m³+ n²).

2 – O tempo de execução T(n) de um algoritmo, em que n é o tamanho da entrada, é dado pela equação de recorrência T(n) = 8T(n/2)+q*n se n > 1. Dado que T(1) = p, e que p e q são constantes arbitrárias, a complexidade do algoritmo é:
A) O(n).
B) O(n log n).
C) O(n²).
D) O(n³).
E) O(n ^ n).

3 – Em relação ao limite assintótico de notação O, atribua V (verdadeiro) ou F (falso) às afirmativas a seguir.
(  ) Em uma estrutura de laço duplamente aninhado, tem-se imediatamente um limite superior O(n²).
(  ) Em uma estrutura de laço duplamente aninhado, o custo de cada iteração do laço interno é de limite
superior O(1).
(  ) Em uma estrutura de laço triplamente aninhado, o custo de cada iteração do laço interno é de limite
superior O(n³).
(  ) O limite O(n²) para o tempo de execução do pior caso de execução aplica-se para qualquer entrada.
(  ) f(n) = O(g(n)) é uma afirmação de que algum múltiplo constante de g(n) é de limite assintótico
inferior.
Assinale a alternativa que contém, de cima para baixo, a sequência correta.
a) V, V, F, V, F.
b) V, F, V, F, V.
c) F, V, V, F, F.
d) F, F, V, V, F.
e) F, F, F, V, V.

4- A função que caracteriza o custo de tempo de pior caso, T (n), para a chamada ALGSORT(X, 1, n) é
dada por:
a) T(n) = T(n − 1) + 2n − 2
b) T(n) = T(n − 2) + 2n − 2
c) T(n) = T(n − 2) + n − 1
d) T(n) = T(n − 2) + (n − 1)2
e) T(n) = T (n/2) + 2n

5 – Com relação ao projeto do algoritmo ALGSORT, assinale a alternativa correta.
a) O custo de combinação de ALGSORT é O(n) em função do tamanho da entrada para a chamada
ALGSORT(X, 1, n).
b) Modificando o trecho das linhas de (3) a (6) de ALGSORT, é possível obter um algoritmo assintoticamente
menos custoso.
c) O tempo de execução para a chamada ALGSORT(X, 1, n) em função de n é O(n lg n).
d) O tempo de execução de ALGSORT é _(n2) em função de n para a chamada ALGSORT(X, 1, n).
e) O custo do caso base n = 1 para a chamada ALGSORT(X, 1, n) em função de n é T(n) = 1.

6 – Em relação à pesquisa sequencial e binária, assinale a alternativa correta.
a) A pesquisa binária em média percorre a metade dos elementos do vetor.
b) A pesquisa binária percorre no pior caso log2 n elementos.
c) A pesquisa binária pode ser feita sobre qualquer distribuição dos elementos.
d) A pesquisa sequencial exige que os elementos estejam completamente ordenados.
e) A pesquisa sequencial percorre todos os elementos para encontrar a chave.

7- Seja V um vetor de n inteiros não negativos, tal que o maior valor encontrado em V é m > 0.
Com relação à ordenação de V , considere as afirmativas a seguir.
I. O tempo de execução dos algoritmos Quicksort e Mergesort para ordenar V é (n lg n) para qualquer
valor de m.
II. Quando m = O(n), é possível ordenar V em tempo de execução O(n) no pior caso.
III. O tempo de execução de pior caso do Quicksort para ordenar V é O(n lg n) quando m = O(n).
IV. Para instâncias onde n = O(m), o algoritmo Countingsort é mais eficiente que o Mergesort, em função
de n.

Assinale a alternativa correta.
a) Somente as afirmativas I e II são corretas.
b) Somente as afirmativas I e IV são corretas.
c) Somente as afirmativas III e IV são corretas.
d) Somente as afirmativas I, II e III são corretas.
e) Somente as afirmativas II, III e IV são corretas.


8 – Seja Φ (x1, …, xn) o número total de permutações de dois elementos durante a execução do algoritmo QS, inclusive durante as chamadas recursivas. Seja Φ max (n) o maior valor de  Φ (x1, …, xn) para todas as listas possíveis de comprimento n. Sabendo que:

a) Φmax(n) = n – 1
b) Φmax(n) = está em o (n)
c) Φmax(n) = está em O (n log(n)), mas não em O (n)
d) Φmax(n) = está em O (n²), mas não em O (n log n).
e) Φmax(n) > 2n.

9 – Assinale a alternative correta:
a) O tempo de execução do algoritmo QS, no pior caso, para entradas de tamanho n, é de θ (n log2 (n))
b) O tempo de execução total do algoritmo para entrada x1, …, xn é sempre de O (Φ(x1…xn)).
c) O tempo de execução total do algoritmo QS para a entrada x1, …, xn não é proporcional à soma das vezes que cada uma das linhas foi executada.
d) O tempo de execução do algoritmo QS, no pior caso, para entradas de tamanho n, é de θ(n²)
e) O número total de comparações do algoritmo QS, incluindo as chamadas recursivas, é de O (Φmax (n)) no pior caso.

10 – Sejam Ta(n) e Tb(n) os tempos de execução de pior caso de dois algoritmos A e B propostos para um mesmo problema computacional, em função de um certo parâmetro n. Dizemos que o algorimo A é mais eficiente que o algoritmo B assintoticamente no pior caso quando
a) Ta(n) = o (Tb(n)).
b) Tb(n) = o (Ta(n)).
c) Ta(n) = O (Tb(n))
d) Tb(n) = O Ta(n)).
e) Ta(n) = θ(Tb(n)).

11) Considere dois algoritmos A1 e A2, cujas funções de custo são, respectivamente, T1(n) = n² – n + 1 e T2(n) = 6n log2 n + 2n. Para simplificar a análise, assuma que n > 0 é sempre uma potência de 2. Com relação ao enunciado, assinale a alternativa correta.
a) Como T1(n) = θ(n²) e T2 (n) = θ(n log n), então A2 é sempre mais eficiente que A1.
b) O limite superior T1(n) = O (n³) é correto e assintotivamente restrito.
c) O limite inferior T2(n) = Ω(n³) é correto e assintóticamente restrito
d) T1 e T2 são assintoticamente equivalents.
e) A1 é mais eficiente que A2, para n suficientemente pequeno.


12) Considere o problema de ordenação onde os vetores a serem ordenados, de tamanho n > 0, possuem
bn=2c valores iguais a um número real x e dn=2e valores iguais a um outro número real y. Considere que
os números reais x e y são conhecidos e fixos, porém estão distribuídos aleatoriamente no vetor a ser
ordenado.
Neste caso, é correto afirmar:
a) Podemos ordenar estes vetores a um custo O(n).
b) No caso médio, o Quicksort será o algoritmo mais eficiente para este problema, com um custo O(n log n).
c) O algoritmo de ordenação por inserção sempre opera no melhor caso com um custo O(n).
d) O limite inferior para esta classe de problema é (n²) .
e) O limite inferior para esta classe de problema é (n logn).

13) Sejam T1 ( n)=100∙ n + 15, T2 (n)=10 ∙n²+ 2 ∙ n e T3 ( n)=0,5 ∙ n³+ n²+ 3 as equações que descrevem a complexidade de tempo dos algoritmos Alg1, Alg2 e Alg3, respectivamente, para entradas de tamanho n. A respeito da ordem de complexidade desses algoritmos, pode-se concluir que:
(A) as complexidades assintóticas de Alg1, Alg2 e Alg3 estão, respectivamente, em O(n), O(n²) e O(n³).
(B) as complexidades assintóticas de Alg1, Alg2 e Alg3 estão, respectivamente, em O(n), O(n²) e O(n²).
(C) as complexidades assintóticas de Alg1, Alg2 e Alg3 estão, respectivamente, em O(100) ,O(10) e O(0,5).
(D) Alg2 e Alg3 pertencem às mesmas classes de complexidade assintótica.
(E) Alg1 e Alg2 pertencem às mesmas classes de complexidade assintótica.

Respostas

1) A
2) D
3) A
4) B
5) D
6) B
7) A
8) C
9) D
10) A
11) E
12) A
13) A