Complexidade de Algoritmos
• Forma de medir a complexidade de um algoritmo
• Utilizando-se a notação do Big-O, a ordem de
magnitude da expressão n2 + n é O(n2).
• A notação do Big-O pode ser derivada de f(n)
utilizando os seguintes passos:
1. Para termo da função, deixe seu coeficiente igual à 1
2. Mantenha o maior termo da função e descarte os
outros termos. Os termos são classificados da mais
baixa para a mais alta importância como mostrado a
seguir : Log n, n, nlog n, n2, n3, . . ., nk , 2n, n!
Complexidade - Exemplo
• Calcular a notação do Big-O da seguinte função:
• Primeiramente, é assumido que os coeficientes
sejam iguais ao valor 1:
• Em seguida são removidos os fatores de
importância mais baixa. Finalmente, a função
original na notação Big-O fica:
• O(f(n)) = O(n2)
Complexidade - Comparações
• A procura binária é de ordem O(log2n)
• A procura seqüencial é de ordem O(n)
• Tanto a ordenação por borbulhamento como
ordenação de seleção direta são da ordem O(n2)
Complexidade - Comparações
• Como comparar grandezas de crescimento
logarítmico, linear, logarítmico linear, quadrático,
polinomial, exponencial e fatorial?
• Construindo um quadro de comparação
assumindo instruções com velocidade de 1
microsegundo e 10 instruções num loop
Complexidade - Análise
• Considere dois algoritmos que fazem soma e
multiplicação de duas matrizes
linha  1
enquanto ( linha ≤ tamanho_da_matriz) faça
col  1
enquanto (col ≤ tamanho_da_matriz) faça
m3 [linha,col]  m1 [linha , col] + m2 [linha,col]
col
 col + 1
fim_enquanto
linha  linha + 1
fim_enquanto
• Os “enquantos” interno e externo são
dependentes do tamanho da matriz
• Portanto, a eficiência do algoritmo acima é: O
(tamanho da matriz2) ou O(n2)
Complexidade - Análise
• Agora a multiplicação
linha
 1
enquanto (linha ≤ tamanho_da_matriz) faça
col
 1
enquanto (col ≤ tamanho_da_matriz) faça
m3 [linha, col ]
 0
k  1
enquanto (k ≤ tamanho_da_matriz) faça
m3 [linha, col]
k
 m3[linha, col] + m1[linha,k] * m2 [k, col]
 k +1
fim_enquanto
col
 col +1
fim_enquanto
linha  linha +1
fim_enquanto
•Três estruturas de repetição aninhadas tem uma
eficiência na notação Big-O como: O(tamanho da
matriz3) ou O(n3)