Seguindo o assunto da análise de complexidade de algorítimos, vamos começar analisando um problema clássico que é o de ordenar números naturais de um determinado arranjo de entrada em um arranjo semelhante, entretanto, ordenado de forma crescente. Existem várias abordagens clássicas que solucionam esse problema, mas, precisamos aqui de apenas duas para poder analisar as suas complexidades e estabelecer o "melhor" neste caso. Inicialmente vamos ver o algorítimo que faz isso por inserção. Ele se chama Insertion-Sort. O problema a ser resolvido é: dado um arranjo A[ a1, a2, a3 ... an ] organizar o arranjo A de forma que A[a1 < a2 < a3 < .... < an]. Segue o pseudo-código de um dos algorítimos que se propõem a realizar esta tarefa:
1- for
j = 2 to A.comprimento
2- k = A[ j ]
3- i = j - 1
4- while i > 0 e A[ i ]> k
5
- A[
i + 1] = A[
i ]
6- i = i - 1
7- A[ i + 1 ] = k
Este algorítimo começa com o índice j assumindo o valor 2 inicialmente, uma vez que a primeira posição no array já está ordenada. A variável k guarda o valor da posição que está sendo ordenada. O valor do índice i é empurrado uma posição de cada vez para a direita desde que ele seja maior que 0 e seu valor no arranjo maior que a varável k o que implica ser maior que j já que nesta altura da execução k = j.
fig.: i j
1,2,3,4,5
A [5|4|7|9|2]
A corretude (funcionamento correto) deste algorítimo pode ser comprovada aplicando uma técnica semelhante a indução matemática chamada de invariante de laço (loop invariant) com a qual demonstramos o funcionamento do algorítimo. Os passos da invariante de laço são três:
1- Inicialização: Onde a propriedade é verdadeira antes da primeira iteração
2- Manutenção: Se é verdadeiro antes da primeira iteração, será verdadeiro antes da próxima iteração
3- Término: Quando o loop acaba, a invariante nos fornece o resultado do loop, uma propriedade útil.
Observe no algorítimo que a primeira propriedade está comprovada pois se j = 1, o arranjo 1 até j está ordenado pois só tem um componente que é ele mesmo. A manutenção também é verdade por hipótese, uma vez que é verdade antes da primeira iteração. Agora, executando j a partir do índice 2 mostramos que o loop funciona quando ele retorna um valor útil indicando o término com sucesso. A invariante de laço é usada para provar algorítimos iterativos, porém, quando tratamos de algorítimos recursivos, como o próximo que veremos, o merge-Sort, usamos de fato, a indução matemática para mostrar que a função recursiva funciona. No próximo post, continuamos a análise verificando a complexidade do mesmo.
Algorítimos, Cormen, et al, 2012 3ed. capítulo 2.
