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.