[Curso de AeED - Aula 08] [Algoritmo] Ordenação - Inserção

Esta página procura explicar o que é análise de algoritmos. A explicação usa o algoritmo de ordenação por inserção como exemplo.  Esse algoritmo resolve o seguinte
Problema da ordenação:  Rearranjar um vetor A[1..n] de modo que ele fique em ordem crescente.
A página é baseada na seção 2 do capítulo 2 do CLRS.

Ordenação por Inserção

Eis um algoritmo que resolve o problema da ordenação:
Ordenação-Por-Inserção (An)
1   para  j crescendo de 2  até  n  faça
2   x ← A[j]
3   i ← j−1
4   enquanto  i > 0  e  A[i] > x  faça
5   A[i+1] ← A[i]
6   i ← i−1
7   A[i+1] ← x

Veja uma implementação do algoritmo em C:

void insertionSort(int vectorToSort[], int sizeOfVector){
    int i, j, tmp;
    for (i = 1; i < sizeOfVector; i++) {
        j = i;
        while (j > 0 && vectorToSort[j - 1] > vectorToSort[j]) {
            tmp = vectorToSort[j];
            vectorToSort[j] = vectorToSort[j - 1];
            vectorToSort[j - 1] = tmp;
            j--;
        }
    }
}

Análise 1: O algoritmo funciona?

A melhor maneira de mostrar que um algoritmo iterativo faz o que promete é exibir um bom invariante do processo iterativo.  No presente caso, isso é fácil:  no início de cada repetição do para, imediatamente antes de verificar a condição i > 0 e A[i] > x,
o vetor  A[1.. j−1]  é crescente.
Esse invariante é trivialmente verdadeiro na primeira repetição do para (pois j = 2 nesse caso).  Se o invariante for verdadeiro na última repetição do para(quando j = n+1) então nosso problema está resolvido.
1crescentej−1jn
444555555666777222999222999222999

Análise 2: Quanto tempo consome?

A pergunta fundamental da análise de algoritmos é Quanto tempo o algoritmo consome?  À primeira vista, a pergunta não faz sentido porque o tempo depende
  1. da instância do problema, ou seja, do particular vetor A[1..n] sendo ordenado e
  2. da máquina (computador) sendo usada.
Para responder à primeira objeção, digo que estou interessado no pior caso:  para cada valor de n, considero a instância A[1..n] para a qual o algoritmo consome mais tempo.  Vamos denotar esse tempo por T(n).
Para responder à segunda objeção, observo que o tempo não depende tanto assim do computador. Ao mudar de um computador para outro, o consumo de tempo do algoritmo é apenas multiplicado por uma constante. Por exemplo, se T(n) = 250n2 em um computador, então T(n) = 500n2 em um computador duas vezes mais lento e T(n) = 25n2 em um computador dez vezes mais rápido.
Podemos tratar então da determinação de T(n) para o algoritmo de inserção. A coluna direita da figura abaixo registra o número de execuções de cada linha no pior caso.
Ordenação-Por-Inserção (An)     
 para j crescendo de 2 até n façan
 x ← A[j]n−1
 i ← j−1n−1
 enquanto i > 0 e A[i] > x faça2+3+...+n
 A[i+1] ← A[i]1+2+3+...+n−1
 i ← i−11+2+3+...+n−1
 A[i+1] ← xn−1
Suponha agora que a execução de qualquer das linha do código consome 1 unidade de tempo. Então o tempo no pior caso será a soma da coluna direita da figura:
T(n) = (3/2)n2 + (7/2)n − 4.
Se tivéssemos levado em conta o tempo exato de execução de cada linha, obteríamos coeficientes diferentes de 3/2, 7/2 e −4, mas a expressão de T(n) ainda seria da forma an2 + bn + c.
O coeficiente 3/2 de n2 não é importante: ele não depende do algoritmo mas de nossa hipótese 1 unidade de tempo por linha. Já o n2 é fundamental: ele é característico do algoritmo em si e não depende nem do computador nem dos detalhes da implementação do algoritmo. Em resumo, a única parte importante em T(n) é o n2. Todo o resto depende da particular implementação do algoritmo e do particular computador que estivermos usando. Dizemos que a quantidade de tempo que o algoritmo Ordenação-Por-Inserção consome no pior caso é
Θ(n2) .
Dizemos que o algoritmo é quadrático.

Exercícios

  1. [Importante]  Seja N(n) o número de execuções, no pior caso, da atribuição A[i+1] ← A[i] na linha 5 de Ordenação-Por-Inserção.  Mostre que N(n) = n(n−1)/2.  (Observe que o consumo de tempo do algoritmo no pior caso é proporcional a N(n).)
  2. Refaça o exercício da soma de quadrados na página de exercícios preliminares.

Muito vago?

Se você perguntar a um computólogo quanto tempo o algoritmo Ordenação-Por-Inserção consome (no pior caso) para processar um vetor com n elementos ele dirá Θ(n²). Você traduz isso mentalmente para
existem números positivos c e d tais que o consumo de tempo do algoritmo fica entre  cn²  e  dn²  desde que n seja suficientemente grande.
À primeira vista a resposta parece muito vaga. Mas é impossível dar uma resposta mais precisa  (a menos que se conheça muito bem o computador que será usado para executar o algoritmo).
A resposta é até bastante informativa num sentido relativo: ela garante que se o tamanho do vetor for multiplicado por 10, então o tempo de execução será multiplicado por 100  (desde que n seja suficientemente grande);  isso não é tão agradável quanto multiplicar o tempo por 10, mas é menos desastroso que multiplicar o tempo por 1000.

Adendo: versão recursiva da ordenação por inserção

Eis uma versão recursiva do algoritmo de ordenação por inserção:
Inserção-Rec (An)
1   se  n > 1  então
2   Inserção-Rec (An−1)
3   x ← A[n]
4   i ← n−1
5   enquanto  i > 0  e  A[i] > x  faça
6   A[i+1] ← A[i]
7   i ← i−1
8   A[i+1] ← x
Quanto tempo ele consome? Digamos que o consumo de tempo no pior caso é T(n). A figura abaixo dá o tempo de execução de cada linha do algoritmo, supondo que cada execução de uma linha (exceto a linha 2) consome 1 unidade de tempo.
Inserção-Rec (An)      
 se n > 1 então1
 Inserção-Rec (An−1)T(n−1)
 x ← A[n]1
 i ← n−11
 enquanto i > 0 e A[i] > x façan
 A[i+1] ← A[i]n−1
 i ← i−1n−1
 A[i+1] ← x1
É claro então que T satisfaz a recorrência
T(n)  =  T(n−1) + 3n + 2
para n = 2, 3, 4, etc.,  com valor inicial T(1) = 1.  Já mostrei em outra página que uma fórmula fechada para T(n) é
T(n)  =  3n2/2 + 7n/2 − 4.
Eu poderia ter simplificado as coisas. Se estou apenas interessado em saber que T(n) = Ο(n2), bastaria ter verificado, por indução a partir da recorrência, que
T(n)  ≤  2n2 ,
para n = 2, 3, 4, etc.  E isso é fácil.  (Foi necessário um pouco de experimentação para casar o coeficiente 2 na frente de n2 com o valor inicial 2 de n.)

Exercícios

  1. Prove, diretamente a partir da recorrência que define T, que T(n) ≤ 7n2/4 para n = 100, 101, etc.
  2. [Importante]  Seja N(n) o número de execuções, no pior caso, da atribuição A[i+1] ← A[i] na linha 6 de Inserção-Rec.  (Esse número é interessante porque é proporcional ao consumo de tempo do algoritmo no pior caso.)  Mostre que N satisfaz a recorrência
    N(n) = N(n−1) + n−1
    para n = 2, 3, 4, 5, etc.  com valor inicial N(0) = N(1) = 0.  Deduza daí que  N(n) = n²/2 − n/2  para todo n natural não nulo.
  3. Seja N a função definida pela recorrência  N(n) = N(n−1) + n−1  para n = 2, 3, 4, 5, etc.  com valor inicial N(1) = 0.  Prove diretamente a partir da recorrência que N(n) ≤ n² para todo n natural não nulo.

Mais exercícios

  1. Consider o problema de colocar em ordem crescente um vetor A[1..n]. Escreva um algoritmo de ordenação por seleção para resolver o problema.  (A ideia do algoritmo é a seguinte: no início de cada iteração, A[1.. j−1] está em ordem crescente e contém os elementos pequenos; o vetor A[j..n] contém os elementos grandes.)  Escreva uma versão iterativa e uma recursiva do algoritmo. Faça uma análise do tempo de pior caso do algoritmo.




Referências
[Curso de AeED - Aula 08] [Algoritmo] Ordenação - Inserção [Curso de AeED - Aula 08] [Algoritmo] Ordenação - Inserção Reviewed by Vinicius dos Santos on 10:36:00 Rating: 5

Nenhum comentário

Escreve ai sua opinião!