Logo Passei Direto
Buscar

Complexidade de algoritmo

Ferramentas de estudo

Questões resolvidas

b. ORDENA (N, A) para i de 1 até (N – 1) repita para j de 1 até (n – i ) repita se A[ j ] > A[ j + 1 ] então x ← A[ j ] A[ j ] ← A[ j + 1 ] A[ j + 1 ] ← x
Qual a complexidade do algoritmo ORDENA?

c. n ← 1 enquanto (n ≤ 10) faça k ← 1 enquanto ( k ≤ 10 ) faça ... trecho de pseudocódigo k ← K + 1 fim-enquanto n ← n + 1 fim-enquanto
Qual a complexidade do algoritmo descrito?

Material
páginas com resultados encontrados.
páginas com resultados encontrados.

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Questões resolvidas

b. ORDENA (N, A) para i de 1 até (N – 1) repita para j de 1 até (n – i ) repita se A[ j ] > A[ j + 1 ] então x ← A[ j ] A[ j ] ← A[ j + 1 ] A[ j + 1 ] ← x
Qual a complexidade do algoritmo ORDENA?

c. n ← 1 enquanto (n ≤ 10) faça k ← 1 enquanto ( k ≤ 10 ) faça ... trecho de pseudocódigo k ← K + 1 fim-enquanto n ← n + 1 fim-enquanto
Qual a complexidade do algoritmo descrito?

Prévia do material em texto

Instituto Federal da Bahia – IFBA 
Campus Vitória da Conquista 
Exercícios de complexidade de algoritmos 
1. Sabendo que um algoritmo possui complexidade O(3m³ + 2mn² + n² + 10m + m²). Qual a 
maneira simplificada de representar a complexidade desse algoritmo? 
R. O(m³ + mn²). 
 
2. Sejam T1(n)=100n+15, T2(n)=10n²+2n e T3(n)=0,5n³+n²+3 as equações que descrevem a 
complexidade de tempo dos algoritmos A1, A2 e A3, respectivamente, para entradas de tamanho 
n. Determine a ordem de complexidade desses algoritmos. 
 
R. T1(n) é O(n), T2(n) é O(n2) e T3(n) é O(n3), eles são respectivamente, polinômios de 
primeiro, segundo e terceiro grau. 
 
3. Considere dois algoritmos A1 e A2, cujas funções de custo são, respectivamente, T1(n) = n²-n+1 
e T2(n) = 6nlog2n+2n. Determine a ordem de complexidade deles. 
 
R. A1 é mais eficiente que A2, para n suficientemente pequeno. 
 
4. Suponha que você tenha dois algoritmos, A1 e A2, com complexidade n5 e 2n, respectivamente. 
Você utilizaria o algoritmo B ao invés do A em algum caso? Qual? 
R. Sim, ainda que o alritmo seja exponencial, quando o valor de “n” é pequeno, esta função 
produz um tempo de complexidade menor do que a função do algoritmo A. Por exemplo para 
valores de n iguais 2 ... 10 ....20 
 
5. Analise o algoritmo abaixo e responda: MaxMin(vetor v) max=v[1]; min=v[1]; para i=2 até n faça 
se v[1]> max então max=v[1]; 
fimse se v[1]< min 
então min=v[1]; 
fimse 
fimpara; 
fim. 
a. Qual a sua complexidade superior? 
R. O algoritmo é da ordem de complexidade O(n). 
b. Podemos dizer que o algoritmo acima é O(n2)? Justifique 
R. n é O(n2), mas o foco é no limite mínimo superior, então a resposta mais adequada é 
O(n). 
6. Considerando a comparação como operação elementar, determine a complexidade do 
algoritmos abaixo: 
a. MAIOR (N, A) max ← A [ 1 ] para i de 2 até N repita 
 Se max < A[ i ] então 
max ←A[ i ] 
 
 
R. O algoritmo é de 
O(N) 
b. ORDENA (N, A) 
 
 
 
para i de 1 até (N – 1) repita 
para j de 1 até (n – i ) repita 
 se A[ j ] > A[ j + 1 ] 
então x ← A[ j ] A[ j ] 
← A[ j + 1 ] 
 A[ j + 1 ] ← x 
c. n ← 1 
enquanto (n ≤ 10) faça 
 k ← 1 
 enquanto ( k ≤ 10 ) faça 
 ... trecho de pseudocódigo 
k ← K + 1 
fim-enquanto 
n ← n + 1 
fim-enquanto

Mais conteúdos dessa disciplina