INSERTION-SORT, casos de execução e notação Θ

Prévia do material em texto

Estrutura de Dados II - Universidade Federal de Itajubá
Nome: Thiago Augusto da Silva Cortez
Análise de algoritmos
Analisar um algoritmo significa prever os recursos de que o algoritmo
necessitará. Ocasionamente os recursos do computador são a principal
preocupação, mas é o tempo de computação que desejamos medir.
Antes de podermos analisar um algoritmo, devemos ter um modelo da
tecnologia de implementação que será usada, inclusive um modelo dos
recursos dessa tecnologia e seus custos.
Análise da ordenação por inserção
O tempo despendido pelo procedimento INSERTION-SORT depende da
entrada: a ordenação de mil números demora mais que a ordenação de três
números. Além disso, INSERTION-SORT pode demorar períodos diferentes
para ordenar duas sequências de entrada do mesmo tamanho, dependendo
do quanto elas já estejam ordenadas. É tradicional descrever o tempo de
execução de um programa como uma função do tamanho de sua entrada,
usando para isso os termos “tempo de execução” e “tamanho da entrada”.
 Tempo de Execução:
É o número de operações primitivas ou “etapas” executadas. É
conveniente definir a noção de etapa (ou passo) de forma que ela seja tão
independente da máquina quanto possível
 Tamanho da Entrada:
Depende do problema que está sendo estudado. No caso de muitos
problemas, como a ordenação ou o cálculo de transformações discretas
de Fourier, a medida mais natural é o número de itens na entrada e/ou o
tamanho do arranjo n para ordenação. Em outros problemas, a melhor
medida do tamanho da entrada é o número total de bits necessários para
representar a entrada em notação binária comum, e às vezes, é mais
apropriado descrever o tamanho da entrada com dois números em lugar
de um.
Para o procedimento INSERTION-SORT, será adicionado ao documento o
custo de tempo e o número de vezes que cada instrução é executada. Por
exemplo, quando um FOR ou WHILE é executado e terminado pelo
descumprimento do teste lógico do cabeçalho, tal instrução ainda é executada
uma vez mais que o número de vezes que o seu bloco de comandos.
O tempo de execução do algoritmo é a soma dos tempos de execução
para cada instrução executada. Mesmo para entradas de um dado tamanho, o
tempo de execução de um algoritmo pode depender de qual entrada desse
tamanho é dada.
O tempo de execução do melhor caso, pode ser calcuado com an + b para
constantes a e b que dependem dos custos de instrução, assim, ele é uma
função linear de n.
O tempo de execução do pior caso pode ser expresso como an² + bn + c
para constantes a, b e c que, mais uma vez, dependem dos custos de
instrução; portanto, ele é uma função quadrática de n.
Em geral, a ordenação por inserção e o tempo de execução de um
algoritimo é fixo para uma determinada entrada.
Análise do pior caso e do caso médio
Razões de porque o pior caso é importante ser desoberto:
 O tempo de execução do pior caso de um algoritmo é um limite superior
sobre o tempo de execução para qualquer entrada;
 Para alguns algoritmos, o pior caso ocorre com bastante frequência, como
a busca de informações ausentes;
 Muitas vezes, o "caso médio" é quase tão ruim quanto o pior caso, já que
se desenvolvermos o tempo de execução do caso médio resultante, ele
será uma função quadrática do tamanho da entrada, exatamente como o
tempo de execução do pior caso.
Ordem de crescimento
Levando em conta algumas abstrações simplificadoras:
 Ignorar o custo real e o custo abstrato do custo de instrução;
 A taxa de crescimento, ou ordem de crescimento, do tempo de execução,
assim, levaremos em conta apenas o termo inicial da fórmula, já que os
outros termos seriam relativamente insignificantes perto do alto valor do
primeiro termo;
 Ignoramos o coeficiente constante do termo inicial, tendo em vista que
fatores constantes são menos significativos que a taxa de crescimento na
determinação da eficiência computacional para grandes entradas.
Logo, escrevemos que a INSERTION-SORT, por exemplo, tem um tempo
de execução do pior caso igual a Θ.
Em geral, consideramos um algoritmo mais eficiente que outro se o tempo de
execução do seu pior caso apresenta uma ordem de crescimento mais baixa,
assim um algoritmo Θ(n²) executará em menos tempo do que um com Θ(n³).
Exercícios
1. Expresse a função n³/1000 - 100n² - 100n + 3 em termos da notação 0.
R: Será n³, pois podemos ignorar os outros fatores da expressão, já que
terão um valor insignificante perto de n³ e ignoraremos também, de
acordo com os principios apresentados (1/1000).
2. Como podemos modificar praticamente qualquer algoritmo para ter um
bom tempo de execução no melhor caso?
R: A melhor forma de otimizar um algoritmo, ou seja, melhorar seu tempo
de execução no melhor caso, é procurar usar o menor numero possivel de
variaveis, funções e quaisquer outras ações no código que possa
demandar processamento, uso das memórias e outros. Em outras
palavras, seria “enxugar” o máximo possível o código.