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