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.