Divisão e Conquista e Algorítimo Merge-Sort parte 2

Vimos que o número total de elementos a serem intercalados neste passo é r-p+1 e que este também é o tempo levado pelo procedimento MERGE. agora o algorítimo sugerido a seguir faz este procedimento de organizar de forma crescente os subconjuntos de cartas que já estão ordenadas.

MERGE(A, p, q, r)

1    n1= q - p + 1

2    n2= r - q 

3    sejam L[1..n1 + 1] e R[1.. n2 + 1] novos arranjos

4    for i = 1 to n1

5        L[i] = A[p + i - 1]

6    for j = 1 to n2

7        R[j] = A[q + j]

8    L[n1 + 1] = z

9    R[n2 + 1] = z

10    i = 1

11    j = 1

12     for     k = p to r

13        if L[i] <= R[j]

14            then  A[k] = L[i]

15                    i = i + 1

16            else A[k] = R[j]

17                    j = j + 1

    

O algorítimo acima funciona assim: linhas 1 e 2 calculam as extensões dos subarranjos a serem organizados. A linha 3 cria mais dois Arranjos que recebem os L e R. Na linha 4 e 5 copia o Arranjo A[ p .. q]  em L[1 .. n1] e as 6 e 7 faz o mesmo para A[ q + 1 .. r] em  R[1 .. n2]. As linhas 8 e 9 possuem uma nuance interessante. Aplica-se aqui uma carta de nome z que é um marcador indicando uma carta de valor infinito que já não precisa ser ordenada. Estas cartas são colocadas nas extremidades dos arranjos L e R. De 10 a 17 os r - p + 1 passos básicos são executados. 

No próximo post vamos fazer a análise da corretude deste algorítimo e depois implementar o MERGE-SORT de fato, introduzindo a recursividade. Até lá!

Algoritmos / Thomas H. Cormen... [et al.] ; [tradução Arlete Simille Marques]. - Rio de Janeiro : Elsevier, 2012. il.
Tradução de: Introduction to algorithms, 3rd ed.
Cap 2.

Divisão e Conquista e algorítimo Merge-Sort part1

Até aqui, no algorítimo Isertion-Sort usamos uma técnica de projeto de algorítimo chamada incremental, e provamos sua funcionalidade usando a técnica de invariante do laço. Para o algorítimo Merge-Sort usaremos uma técnica chamada de Divisão e Conquista. Esta técnica usa no geral, a recursividade, um método em que o algorítimo chama a si mesmo durante a solução de um problema. A divisão e conquista consiste em dividir o problema em instancias cada vez menores a ponto de ele se tornar bem simples. Após isso, o algorítimo recorre recursivamente a si mesmo pela solução destes pequenos problemas resultantes. No fim, ele combina as mini-soluções em uma solução grande para o problema original. A seguir, veja os três passos para a aplicação da técnica da divisão e conquista:

Dividir: o problema é dividido em subproblemas cada vez menores até se tornarem simples de resolver

Conquista: O algorítimo resolve o problema recursivamente, ou se o problema é pequeno o bastante, resolve direto.

Combinar: as soluções dos subproblemas são combinadas para formar a solução do problema original.

O algorítimo Merge-Sort segue à risca este paradigma. Ele Divide a sequencia a ser ordenada de n elementos em subsequências de n/2 cada, executando o passo da DIVISÃO. Depois segue ordenando as subsequencias recursivamente utilizando a intercalação, o que configura o passo da CONQUISTA. Por último o passo da COMBINAÇÃO que é conseguida intercalando as subsequências de forma a gerar a resposta ao problema original.

A recursividade deixa de existir quando a sequencia tiver cumprimento 1(ou seja, ordenada por si só). O passo mais importante no Merge-Sort é o da combinação onde recorremos ao processo MERGE(A,p,q,r) em que A é um arranjo e p,q,r são índices de enumeração onde p=<q<r partindo da premissa que A[p...q] e A[q+1...r] já estão ordenados. À partir disso, forma-se um único sub-arranjo ordenado que ficará no lugar de A[p...r]. Este procedimento leva um tempo teta(n) onde n= r-p+1. 

No próximo post, o algoritmo MERGE. Até lá!

Algoritmos / Thomas H. Cormen... [et al.] ; [tradução Arlete Simille Marques]. - Rio de Janeiro : Elsevier, 2012. il.
Tradução de: Introduction to algorithms, 3rd ed.
Cap 2.

Ordem de crescimento

Você percebeu que algumas abordagens abstrativas foram usadas para simplificar a análise do Insertio-Sort. Os custos reais foram substituídos por custos abstratos definidos pelas constantes ci. Depois até mesmo estas constantes foram desprezadas porque elas nos davam mais detalhes do que, de fato, precisávamos. Então expressamos o tempo de pior caso como an²+bn+c para constantes a, b e c que dependem dos custos abstratos ci. Porém, ao ignorarmos inclusive este custo abstrato, facilitamos ainda mais a estimativa T(n). Mais uma abstração simplificadora é feita aqui, e definimos assim o que chamamos de taxa de crescimento ou ordem de crescimento. Neste caso, consideramos apenas o primeiro termo an² ou seja, o termo mais significativo, pois os termos de ordem mais baixa são insignificantes para grandes valores. Ignoramos a constante inicial pois não pesa nos cálculos de crescimento. Com toda esta abstração da matemática envolvida, afirmamos que a ordem de crescimento do algorítimo de ordenação por inserção, tem um tempo de execução teta de n ao quadrado e se representa ø(n²). 

ps.: entenda esse simbolo como a letra teta. Meu notebook não tem. 

No futuro, vamos estudar essa notação com mais cuidado. No memento, queremos apenas entender que para comparar a eficiência de um algorítimo com outro, usamos o tempo de execução como parâmetro. Assim, se um algorítimo tem o tempo de execução na ordem ø(n²) e o outro ø(n), então, o segundo algorítimo tem melhor eficiência. Essa ideia será usada quando terminarmos de analisar a complexidade do algorítimo Merge-Sort para definirmos o mais eficiente na tarefa de ordenação.

Algoritmos / Thomas H. Cormen... [et al.] ; [tradução Arlete Simille Marques]. - Rio de Janeiro : Elsevier, 2012. il.
Tradução de: Introduction to algorithms, 3rd ed.
Cap 2.

 

Complexidade de pior caso Insertion-Sort - Parte2

O pior caso resulta de quando o arranjo A está totalmente invertido ou em ordem decrescente. Neste caso a linha 4 será executada tanto quanto for o comprimento do arranjo A menos um, ou seja, j vezes porque neste caso, A[i] > k levando a execução das linhas 5 e 6 j - 1 vezes. Disto resulta o somatório de j=2 até n(j) = [n(n + 1)/2]-1 para a linha 4 e j=2 até n(j-1) = n(n-1)/2 para as linhas 5 e 6. Substituindo na nossa fórmula encontrada no post passado e ignorando a constante que é a mesma e sabemos agora não alterará o que queremos saber, que é complexidade da função, temos:

T(n)= n + (n-1) + (n-1) + [n(n+1)/2]-1 + [n(n-1)/2] + [n(n-1)/2 + (n-1) = 3n^2 + 7/2n - 4 

que é uma função quadrática ou do segundo grau. Assim, a complexidade de pior caso deste algorítimo é de quadrática. A complexidade do caso médio não nos interessa a esta análise e normalmente não é utilizada. No próximo post, evoluímos desta fórmula para uma notação mais simples, a ordem de crescimento da função.

1-            for j = 2 to A.comprimento                                    c1  n

2-                k = A[ j ]                                                             c2 (n-1)

3-                i = j - 1                                                                c3 (n-1)

4-                while i > 0 e A[ i ]> k                                         c4 [n(n+1)/2]-1

5-                        A[ i + 1] = A[ i ]                                         c5 [n(n-1)/2]

6-                         i = i - 1                                                       c6 [n(n-1)/2]

7-                A[ i + 1 ] = k                                                       c7 (n-1)

Algoritmos / Thomas H. Cormen... [et al.] ; [tradução Arlete Simille Marques]. - Rio de Janeiro : Elsevier, 2012. il.
Tradução de: Introduction to algorithms, 3rd ed.
Cap 2.

 

Ordenação Insertion-Sort parte 2 - complexidade de melhor caso

Medimos a complexidade na unidade tempo de execução na maioria das vezes. Em algorítimos como o Insertion-Sort esse tempo de dois fatores: O tamanho da entrada e a ordenação desta entrada. Para ordenar 3 números exige-se um tempo menor do que para ordenar 100. Da mesma maneira, a ordenação destes mesmos números em ordem decrescente leva mais tempo do que se apenas uma parte estiver desordenada. Na análise a seguir, admitamos a constante c em cada linha do pseudo-código como constante de tempo em função da quantidade n de vezes em que esta linha é executada. Daí somamos as resultantes para determinar o tempo de execução. Esta fórmula encontrada será usada para definir uma notação simples para comparar a eficiência de um algorítimo com outro:

linha do pseudo-code                                 constante c de Tempo e número n de vezes da execução

1-            for j = 2 to A.comprimento                                    c1  n

2-                k = A[ j ]                                                             c2 (n-1)

3-                i = j - 1                                                                c3 (n-1)

4-                while i > 0 e A[ i ]> k                                         c4 [n(n+1)/2]-1

5-                        A[ i + 1] = A[ i ]                                         c5 [n(n-1)/2]

6-                         i = i - 1                                                       c6 [n(n-1)/2]

7-                A[ i + 1 ] = k                                                       c7 (n-1)

Associamos ao c o número da linha por razões didáticas. A soma destas linhas é igual ao tempo de execução do algorítimo T(n). 

T(n)= c1n + c2(n-1) + c3(n-1) + c4[n(n+1)/2]-1 + c5[n(n-1)/2] + c6[n(n-1)/2 + c7(n-1) 

percebe-se que o tempo de ordenação fica amarrado ao tamanho da entrada n e eventualmente à sua ordenação. Observe que para uma entrada hipoteticamente totalmente ordenada resulta no que chamamos de melhor caso. Vemos que na linha 4 o valor A[i] será <= k e neste caso nunca entraremos no laço, por consequência, esta linha será executada (n-1) vezes e as linhas 5 e 6 não serão executadas. Portanto, T(n)= c1 + c2(n-1) + c3(n-1) + c4(n-1) + c7(n-1)=

= (c1 + c2 + c3 + c4 + c7)n - (c2 + c3 + c4 + c7)  o que nada mais é que uma função de primeiro grau an+b para duas constantes a e b. Em resumo, o tempo de execução do melhor caso é T(n)=an+b.

A seguir, próximo post, análise do pior caso

Algoritmos / Thomas H. Cormen... [et al.] ; [tradução Arlete Simille Marques]. - Rio de Janeiro : Elsevier, 2012. il.
Tradução de: Introduction to algorithms, 3rd ed.
Cap 2.

Algorítimo de ordenação Insertion-Sort

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.

O que é análise de complexidade de um algorítimo?

Propomos um algorítimo com a finalidade de resolver problemas do mundo real. Porém, não é raro haver várias propostas de algorítimos para resolver o mesmo problema. E aí neste caso, qual o melhor algorítimo? Então buscamos mensurar a quantidade de recursos que um algorítimo precisa para funcionar. Recursos de processamento, memória e às vezes, largura de banda são os que primeiro nos vêm à mente. No entanto, quando analisamos um algorítimo é muito importante analisa-lo levando em conta o tempo de computação. No modelo de computação genérico temos instruções pré-definidas como instruções de soma, subtração, divisão, multiplicação, desvio condicional, carregamento, cópia e muitas outras. Cada instrução dessa leva um tempo constante para ser realizada. Mas, há algumas tarefas que precisam ser construídas, como por exemplo a ordenação de números naturais. Para isso precisamos construir um algorítimo que realize a tarefa com as operações que a máquina já contempla. Dessa forma, vários modos de realizar a mesma tarefa surgem, e analisar a complexidade de cada solução se torna necessário para eleger a mais aplicável aos recursos disponíveis. No próximo post trarei um problema de ordenação e uma solução para ele. A partir daí, iremos analisar esta proposta e determinar a sua complexidade. Depois vamos verificar outra proposta, com uma abordagem diferente, analisar sua complexidade, e inferir qual o mais eficiente. Inicialmente, o faremos de uma forma generalista, e depois usando ferramentas luxuosas de medida de complexidade, tratando o algorítimo como um modelo matemático de solução de problemas.

Algorítimos, Cormen, et al, 2012 3ed. capítulo 2.