Análise de Complexidade de Algoritmos

1. Análise de Complexidade de Algoritmos
1.1 – Conceitos
Análise de Algoritmos é a área da computação que visa determinar a complexidade (custo) de um algoritmo, o que torna possível:
• Comparar algoritmos
• Determinar se um algoritmo é “ótimo”.
Custo de um algoritmo:
• Tempo (número de passos)
• Espaço (memória)
Ex. 1: Organizar uma corda de tamanho T de maneira que ocupe o menor espaço possível. 1. Enrolar no braço
(mesmo comprimento do laço)
2. Enrolar sobre si
(aumentando gradativamente o tamanho do laço)
3. Dobrar sucessivamente
(até que não seja mais possível dobrar)
Qual o método mais eficiente?
A complexidade de um algoritmo é medida segundo um modelo matemático que supõe que este vai trabalhar sobre uma entrada (massa de dados) de tamanho N.
O processo de execução de um algoritmo pode ser dividido em etapas elementares denominadas passos (número fixo de operações básicas, tempo constante, operação de maior freqüência chamada dominante) . O número de passos de um algoritmo é considerado como o número de execuções da operação dominante em função das entradas, desprezando-se constantes aditivas ou multiplicativas. Definimos a expressão matemática de avaliação do tempo de execução de um algoritmo como sendo uma função que fornece o número de passos efetuados pelo algoritmo a partir de uma certa entrada.
Ex. 2: Soma de vetores para I de 1 até N faça
S[I] ← X[I] + Y[I]
Fim para
Número de passos = número de somas (N)
Ex. 3: Soma de matrizes
Para I de 1 até N faça
Para J de1 até N faça
C[I,J] ←A[I,j] + B[I,J]
Fim para
Fim para
Número de passos = número de somas (N*N)
Ex. 4: Produto de matrizes
Para I de 1 até N faça
Para J de 1 até N faça
P[I,J] ←0
Para K de 1 até N faça
P[I,J] ← P[I,J] + A[I,K] * B[K,J]
Fim para
Fim para
Fim para
Número de passos = Número de somas e produtos (N*N*N)
A complexidade pode ser qualificada quanto ao seu comportamento como:
• Polinomial
A medida que N aumenta o fator que estiver