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.
