UNIVERSIDADE FEDERAL DO VALE DO SÃO FRANCISCO – UNIVASF

COLEGIADO DE ENGENHARIA DA COMPUTAÇÃO – CECOMP

RELATÓRIO DE COMPLEXIDADE DE TEMPO E ESPAÇO DE ALGORITMOS

Equipe: Rafael Gonçalves,

Romullo Abizair,

Saulo Rogério.

Juazeiro – BA

Dezembro de 2013

  2  

UNIVERSIDADE FEDERAL DO VALE DO SÃO FRANCISCO – UNIVASF

COLEGIADO DE ENGENHARIA DA COMPUTAÇÃO – CECOMP

RAFAEL GONÇALVES, ROMULLO ABIZAIR, SAULO ROGÉRIO.

RELATÓRIO DE COMPLEXIDADE DE TEMPO E ESPAÇO DE ALGORITMOS

Relatório desenvolvido para a

disciplina Estrutura de Dados II,

ministrada pela professora

Ana Emília Melo Queiroz e

usado como critério de avaliação.

Juazeiro – BA

Dezembro de 2013

  3  

Índice

1. Introdução ........................................................................................................................ 4

2. Esquema Básico de um Algoritmo ................................................................................... 5

3. Tamanho da Entrada ........................................................................................................ 6

4. Tempo de Complexidade de um Algoritmo .................................................................... 6

4.1 Análise do Tempo ...................................................................................................... 6

4.2 Análise do Pior, Médio e Melhor casos ...................................................................... 7

4.3 Algoritmos de Ordenação ........................................................................................... 7

4.4 Comportamento das Funções de Tempo ................................................................... 11

4.5 A Análise Matemática e Empírica .............................................................................. 12

4.6 Gráficos Melhor, Médio e Pior casos ......................................................................... 13

4.7 Resultados da Implementação das Análise Matemática e Empírica .......................... 16

4.8 Limite Inferior e Limite Superior ............................................................................... 16

4.9 A eficiência dos Algoritmos na Obtenção dos Resultados ......................................... 16

5. Espaço de Complexidade de um Algoritmo ....................................................................... 17

6. Conclusão ............................................................................................................................ 18

7. Referências Bibliográficas .................................................................................................. 18

  4  

1. Introdução

Assim como fala [ZIVIANI, 1999], os algoritmos fazem parte do nosso dia-dia.

Instruções, receitas, manuais são exemplos de algoritmos.

Algoritmo de modo resumido é um conjunto sequencial e finito de ações que devem ser

executadas para se chegar num objetivo, ou seja, passos necessários para se chegar a uma

resolução de um determinado tipo de problema. Mas, como para cada problema têm-se uma

resolução, encontramos uma incógnita aqui. Podemos ter uma ou várias resoluções para um

mesmo problema por exemplo, e também cada código terá uma complexidade e um tempo

de execução para se chegar ao objetivo, ou seja, cada algoritmo terá sua sequência de passos

e seu tamanho, diferenciando assim de uma outra resolução.

Já de acordo com [LEISERSON,2002] algoritmo nada mais é do que uma receita que mostra

passo a passo os procedimentos necessários para a resolução de uma tarefa. Com isso,

[LEISERSON,2002] aprofunda-se mais um pouco ao dizer que estrutura de dados está

ligada à escolha do melhor algoritmo para a resolução de uma tarefa, daí levamos em conta

questões como o armazenamento e organização dos dados, assim mostramos que estamos

preocupados com o melhor modo para se chegar ao objetivo, o jeito mais rápido e fácil de se

resolver um problema. Existem vários tipos de estruturas de dados e nenhuma delas

funciona perfeitamente para todos os problemas requisitados, com isso, é importante não só

conhecer cada uma delas mais também escolher melhor aquela que irá proporcionar um

desempenho satisfatório.

Como algoritmos estruturados são organizadamente escritos, não tem como

falarmos de estrutura de dados sem mencionar os algoritmos e suas características, nem

como escrever um algoritmo sem pensar em sua estrutura. De acordo com [ZIVIANI, 1999],

programar é basicamente construir um código e estrutura-lo adequadamente, de acordo com

as necessidades dos usuários.

Mesmo que os computadores atuais tenha configurações boas, as máquinas ainda

tem suas limitações, talvez sua memória seja absurdamente grande, mas certas tarefas ainda

levam muito tempo para serem executadas. Se tivéssemos um super computador que fosse

capaz de executar suas ações incrivelmente rápidos, nós não precisaríamos nos preocupar

com a estruturação de algoritmos para solucionar problemas, porque todos os algoritmos

  5  

teriam seus resultados iguais, e utilizaríamos sempre o método mais rápido e fácil de ser

implementado. Por isso devemos dar atenção a importância de criar algoritmos eficientes em

termos de tempo e de espaço alocado na memória para assim termos os melhores resultados

possíveis.

2. Esquema Básico de um Algoritmo

Como já mencionamos anteriormente, os algoritmos são como espécies de

receitas, nas quais têm-se os passos necessários para se realizar uma tarefa. O ideal é que

esse passo a passo seja claro e objetivo, sem ser ambíguo ou redundantes.

Os algoritmos podem ser construídos através de uma linguagem chamada pseudocódigo, que

tem uma formatação e estrutura mais próxima da escrita humana, ajudando assim aos

iniciantes na programação. Evidenciando-se que um algoritmo independe de linguagens de

programação. Em pseudocódigo, o algoritmo posteriormente servirá como uma ponte para

uma linguagem de programação mais desenvolvida e objetiva.

Segundo [VILLAR, 1993], temos algumas regras que são importantes na construção de um

algoritmo. São elas:

• Ser objetivo

• Supor que você está desenvolvendo um algoritmo para pessoas que não trabalham

conhecem informática

• Utilizar frases simples e curtas

• Usar um verbo por frase

• Usar palavras que não tenham um sentido difícil de se entender ou definir

O esquema da figura abaixo ilustra independente de sua complexidade, como os algoritmos

são implementados:

  6  

3. Tamanho da Entrada

O tamanha da entrada é a quantidade de valores iniciais que serão implementados

e testados nos algoritmos. Dependendo do tipo ou estrutura do algoritmo, uma ordenação de

valores num algoritmo pode ser simples ou complexa, mostrando assim que devemos nos

preocupar em escolher melhor a estrutura para uma determinada quantidade de entrada. Em

alguns casos os algoritmos de ordenação mais simples terão uma maior eficiência que os

mais complexos, como o MergeSort que usa a recursividade em alguns problemas, e como

esta técnica tem um alto consumo de memória e tempo de execução, acaba não sendo muito

eficiente mesmo tendo uma complexidade de tempo menor (MergeSort Θ(n log2 n)). Mas

isso não significa que ele será mais eficiente que um InsertionSort, que tem sua

complexidade de tempo Θ (n2).

4. Tempo de Complexidade de um Algoritmo

4.1 Análise de Tempo

[ZIVIANI,2004] revela que uma das problemáticas que tem que ser resolvida pelo projetista é a questão da análise do tempo de execução de um dado algoritmo, que pode ser medido diretamente, apesar de ser considerada uma medida inadequada, por depender do compilador, do hardware, utilização de memória, serve para casos particulares, onde existem vários algoritmos para um mesmo problema. A forma mais adequada, seria o uso da função de complexidade, onde é possível ignorar o custo de algumas operações envolvidas, que venham a ser irrelevantes. Esta

  7  

análise é importante, para desenvolver soluções mais rápidas, e que gastem menos recursos do computador, poupando memória por exemplo.

4.2 Análise do Pior, Médio e Melhor Casos

Segundo [MARCO, 2001] em sua dissertação, deixa transparecer que:

• Análise no pior caso.

Refere-se ao número máximo de operações fundamentais que devem ser feitas para a

resolução de qualquer problema do tamanho fixado.

Pode ser considerado como um limite de complexidade que não será ultrapassado, sendo

portanto, uma garantia de qualidade mínima do algoritmo. Sua desvantagem é que os casos

caóticos que dificilmente vão acontecer são levados em consideração, nessa análise.

• Análise no Caso Médio

É mais difícil de determinar do que a complexidade no pior caso. Porque baseia-se nas

distribuições probabilísticas dos dados de entrada do algoritmo, que nem sempre são

conhecidas. Esta análise é indicada para algoritmos que são utilizados com frequência.

Os algoritmos que não possuem nenhuma estrutura condicional apresentam complexidades

no pior caso e caso médio, iguais, porque será executada, sempre o mesmo número de

operações para um mesmo tamanho de entrada.

• Análise no melhor caso

De acordo com [ZIVIANI,2004], o melhor caso é dado a partir do menor tempo de

execução sobre todas as entradas de tamanho n.

4.3 Algoritmos de Ordenação

4.3.1 BubbleSort

É o método mais simples em termos de implementação, porém é o

menos eficiente. A idéia principal do algoritmo é percorrer o vetor n − 1 vezes, a cada

passagem fazendo flutuar para o início o menor elemento da sequência. Essa movimentação,

percorrendo o array fazendo comparações e trocas sucessivas lembra a forma como as

bolhas procuram seu pulam de um nível para o outro, por isso o nome do algoritmo.

  8  

Seu uso não é recomendado para vetores com muitos elementos.

Este método pode ser melhorado devido à questão de que os

elementos nas posições acima ou iguais a n - i já estão na ordem correta depois da iteração i,

(ou seja cada iteração garante que pelo menos mais um elemento encontrou a posição

desejada)por isso eles não precisam ser considerados nas próximas iterações. Dessa maneira,

na primeira vez q o algoritmo percorre o array, só é feita a comparação entre os dois

primeiros elementos. [TENEBAUM, 1995]. O melhor caso quando utilizamos este método

se dá apenas quando o arquivo está completamente ordenado, fazendo n – 1 comparações e

nenhuma troca, percorrendo o array uma única vez. Encontramos o Pior caso quando o array

está em ordem reversa, ou seja, quando o késimo passo faz n - k comparações e trocas,

sendo necessário n – 1 passos.

Um dado curioso a cerca da ineficiência deste método acontece quando o array está

praticamente ordenado e apenas o menor dos elementos está na última posição. Desta

maneira o será realizado o mesmo número de comparações do pior caso.

4.3.2 InsertionSort

Segundo [QUEIROZ, 2009], a classificação por inserção é um método

in place que separa o vetor de entrada em dois subvetores, movendo os registros do subvetor

não-ordenado para o vetor ordenado, sendo o último acrescido de um elemento a cada

iteração. [ZIVIANI, 2004] comenta que em cada passo, a partir de i=2, o i-ésimo item do

vetor não-ordenado é apanhado e inserido no seu lugar apropriado dentro do vetor ordenado.

  9  

Esse é um dos métodos mais utilizados entre os jogadores de cartas, por ser fácil de ser

implementado. A complexidade do algoritmo é da ordem O(n²) [ZIVIANI, 2004].

4.3.3 SelectionSort

De acordo com Ziviani, é um dos métodos de ordenação mais simples,

possui um tempo de execução linear no tamanho de entrada. Quando o arquivo já está

ordenado o custo é quadrático. É um método interessante para arquivos pequenos.

4.3.4 ShellSort

[ZIVIANI, 2004] explica que o shellsort é uma extensão do algoritmo

de ordenação por inserção. Entretanto, na classificação por inserção, se o menor item do

vetor de origem estiver na posição mais à direita, então o número de comparações e

movimentações é igual a (n-1) para encontrar o seu ponto de inserção.

A estratégia utilizada pelo shellsort para contornar este problema foi permitir trocas de

registros que estão distantes um do outro. Os itens que estão separados h posições são

rearranjados de tal forma que todo h-ésimo item leva a uma sequência ordenada.

Alguns autores chamam h de “salto”, que pode ser constante ou pode variar de acordo com

uma lógica previamente escolhida. Várias sequências para h têm sido experimentadas.

[KNUTH, 1973] mostrou experimentalmente que a escolha do incremento para h = {1, 4,

13, 40, 121, 364, 1093, 3280, ...} é difícil de ser batida por mais de 20% em eficiência no

tempo de execução.

Shellsort é uma ótima opção para arquivos de tamanho moderado (da ordem de 5000

registros), segundo ZIVIANI, tanto pela fácil implementação do código como pelo tempo de

classificação.

Quanto à sua complexidade, existem duas conjecturas tratadas por ZIVIANI: C(n) =

O(n1,25) e C(n) = O(n*log2(n)). O autor explica que o algoritmo possui em sua

complexidade problemas matemáticos difíceis de resolver e ninguém conseguiu prová-la

ainda.

4.3.5 QuickSort

Consiste em dividir o problema de ordenar um conjunto de n itens em

2 problemas menores, os problemas menores são ordenados e depois os resultados são

combinados para produzir a solução do maior problema. (Dividir para conquistar !) Este

método é ineficiente para arquivos já ordenados com pivô inadequado, pois as partições

  10  

serão desiguais , e a função de ordenação será chamada n vezes, sendo que em cada uma

dessas só conseguirá eliminar um item por chamada, fazendo com que o número de

comparações passe a ser cerca de n2/2. O melhor caso acontece quando o arquivo é dividido

em duas partes iguais, este método requer uma pequena pilha, que servirá como memória

auxiliar, e ordenar um vetor com n itens, com cerca de nlog n operações.

4.3.6 MergeSort

O conceito de merging ou fundir é complementar ao conceito de

selecionar, visto anteriormente, quando se trata de algoritmos de ordenação. [SEDGEWICK,

1998] trata do termo como combinar dois arquivos [vetores] ordenados para formar um

maior que os anteriores também ordenado. Esse conceito faz parte da ideia de “dividir e

conquistar”, muito utilizado na ordenação de registros.

No caso do merge sort, a divisão é feita utilizando recursividade, armazenando os dados do

vetor original na pilha em forma de árvore binária, segundo [Queiroz, 2009]. Após a divisão,

cada subvetor ordenado é recombinado com outro intercalando os elementos, mantendo-se a

ordenação. Esse algoritmo é considerado de ordenação externa, pois se utiliza de outro

espaço da memória para efetuar a classificação.

[SEDGEWICK, 1998] ainda trata de alguns fatores que tornam o merge sort atrativo. Dentre

eles está o fato de que o tempo de execução para um vetor de n elementos é da ordem de

n*log(n). Outro fator observado pelo autor é que o algoritmo é estável, o que significa dizer

que independentemente do tamanho da entrada, a saída será sempre proporcional a n*log(n).

4.3.7 HeapSort

Utilizando o mesmo princípio do SelectSort, o HeapSort é um

algoritmo que utiliza uma estrutura de dados conhecida como Heap binário para manter o

próximo item a ser selecionado. Criado em 1964 por Robert W. Floyd e J.W.J. Williams, ele

é um algoritmo de Ordem de Complexidade O(n log n).

Existem dois tipos de heaps: Os heaps de máximo (max heap), em que

o valor de todos os nós são menores que os de seus respectivos pais; e os heaps de mínimo

(min heap), em que o valor de todos os nós são maiores que os de seus respectivos pais.

Assim, em um heap de máximo, o maior valor do conjunto está na raíz da árvore, enquanto

no heap de mínimo a raíz armazena o menor valor existente. Os heaps podem ser

representados por arranjos, nesse caso a maior (menor) chave está sempre na posição 1 do

array. Os algoritmos para implementar as operações sobre o heap operam ao longo de um

dos caminhos da árvore, a partir da raiz até o nível mais profundo da árvore.

  11  

A figura abaixo mostra um exemplo de um HeapSort:

4.4 Comportamento das Funções de Tempo

[ZIVIANI,2004] Afirma que as funções de tempo são medidas a partir da

complexidade de um dado algoritmo, dadas pela notação do BIG O, cuja notação é definida

como um função g(n) O( f (n)) para alguma constante c > 0 a expressão 0 ≤ g(n) ≤ cf(n) é

válida.

As principais funções de complexidade:

• n f(n) = O(1)

Algoritmos de complexidade O(1) são ditos de complexidade constante.

• n f(n) = O(log n)

Um algoritmo de complexidade O(log n) é dito ter complexidade logarítmica.

Típico em algoritmos que transformam um problema em outros menores.

• n f(n) = O(n)

Um algoritmo de complexidade O(n) é dito ter complexidade linear

Cada vez que n dobra de tamanho, o tempo de execução dobra. n f(n) = O(n log n)

  12  

Típico em algoritmos que quebram um problema em outros menores, resolvem cada um

deles independentemente e ajuntando as soluções depois.

• n f(n) = O(n2)

Um algoritmo de complexidade O(n2) é dito ter complexidade quadrática.

Ocorrem quando os itens de dados são processados aos pares, muitas vezes em um anel

dentro de outro.

• n f(n) = O(n3)

Um algoritmo de complexidade O(n3) é dito ter complexidade cúbica.

Úteis apenas para resolver pequenos problemas.

• n f(n) = O(2n)

Um algoritmo de complexidade O(2n) é dito ter complexidade exponencial.

Geralmente não são úteis sob o ponto de vista prático.

• n f(n) = O(n!)

Um algoritmo de complexidade O(n!) é dito ter complexidade exponencial,

apesar de O(n!) ter comportamento muito pior do que O(2n).

4.5 Análise Matemática e Empírica

Análise empírica baseia-se no desenvolvimento de uma implementação correta e

completa do algoritmo e depende não apenas da natureza dos dados de entrada utilizados

durante a experimentação, mas também de outros fatores que têm influência no

experimento. Como o ambiente de execução utilizado, considerando as máquinas, os

compiladores e os sistemas utilizados durante os experimentos. Enquanto que a análise

matemática é uma alternativa à análise empírica, sendo especialmente útil quando a análise

experimental consome uma quantidade significativa de tempo ou quando necessitamos de

alguma indicação de eficiência antes de qualquer investimento de desenvolvimento.

De acordo com [SEDGEWICK,1998], ele comenta que a análise matemática pode

trazer mais informações e ser mais barata que a análise empírica, que em alguns casos pode

ser suficiente.

  13  

Com a metodologia utilizada, espera-se obter o tempo médio da ordenação de um conjunto

de entradas, aplicado aos algoritmos analisados. Assim poderemos comparar a praticidade

com que os algoritmos podem ser utilizados. Devido ao experimentos iniciais de duração

prolongada, foram criados dois conjuntos de entradas para serem executados pelos

algoritmos “eficientes” e pelos “menos eficientes”.

Os algoritmos foram subdivididos em dois grupos: 1 – Bubble, Selection e Insertion.

2 – Quick, Merge, Heap e Shell.

Paro o grupo 1, foi utilizado o seguinte conjunto de entradas em elementos int: 30.000;

60.000;120.000;240.000;480.000 e 960.000

Paro o grupo 2, foi utilizado o seguinte conjunto de entradas em elementos int: 30.000;

60.000;120.000;240.000;480.000;960.000 e 2.000.000

4.6 Gráficos do Melhor, Médio e Pior casos

  14  

  15  

  16  

4.7 Conclusões sobre análise empírica e matemática

Podemos concluir que à medida que o número de elementos aumenta, o

desempenho diminui e o tempo em milissegundos, aumenta. Tomando “N” como o tamanho

do vetor, com exceção dos métodos, no melhor caso, BubbleSort que verifica se o seu

sucessor é maior, e o InsertionSort que verifica se seu antecessor é menor, N-1 vezes.

O método que no geral, apresentou o melhor desempenho, foi o ShellSort.

4.8 Limite Inferior e Limite Superior

O limite superior de complexidade diz respeito ao melhor algoritmo conhecido que o resolva. Enquanto o limite inferior de complexidade diz respeito a quantidade mínima necessária de recursos para a resolução do problema.

4.9 Eficiência dos Algoritmos

Cada autor tem seu próprio conceito do que é um algoritmo, mais podemos

resumir todos estes conceitos em um, algoritmo nada mais é do que uma receita que mostra

passo a passo os procedimentos necessários para a resolução de uma tarefa. Em termos mais

técnicos, um algoritmo é uma sequência lógica, finita e definida de instruções que devem ser

seguidas para resolver um problema ou executar uma tarefa, e com isso vem outra questão,

podem existir inúmeros tipos diferentes de procedimentos que levem a resolução de um

mesmo problema, cada procedimento terá uma complexidade e um tempo de duração para

se chegar ao objetivo, ou seja, cada algoritmo tem sua sequência própria de passos e seu

tamanho. Quando levamos em conta as questões como o armazenamento de dados e

Como podemos definir se um algoritmo é melhor que o outro assumindo que todos sejam

eficazes, devemos então verificar qual é o mais eficiente. Eficiência pode ser definida como

a capacidade de se atingir um resultado correto, utilizando a menor quantidade de recursos e

tempo possível. Uma das formas de se analisar o tempo de execução de um algoritmo é

conhecida como análise assintótica, ou cálculo da eficiência assintótica, em que se procura

encontrar uma tendência no tempo de execução, quando o volume de dados de entrada do

problema tende ao infinito. Todos esses conjuntos de ferramentas de análise fazem parte de

uma área de conhecimento que visa não apenas entender as limitações dos algoritmos, mas

também melhorar a qualidade e a eficiência do software desenvolvido. Todo desenvolvedor

deveria saber utilizar corretamente estas ferramentas e organiza-los de forma coerente,

mostramos que estamos preocupados com o melhor

  17  

se estes dados estão no caminho para se chegar ao objetivo, que é o jeito mais rápido e fácil

de se resolver um problema. Existem vários tipos de estruturas e nenhuma delas funciona

bem para todos os propósitos, e com isso é importante não só conhecer cada uma delas mais

também escolher aquela que irá proporcionar um melhor desempenho.

O tipo de estrutura a ser utilizada em um algoritmo está relacionado principalmente

com o tamanho de sua entrada, um exemplo disso é o tipo de ordenação que será

utilizada em uma lista, dependendo do tamanho de itens a serem inseridos na lista a

ordenação poderá ser simples, como exemplo o Insertion sort, Selection sort ou

Bubble sort, ou uma ordenação mais complexa como o Quick sort ou Merge sort,

em certos casos os algoritmos de ordenação mais simples terão uma maior eficiência que os

mais complexos, como o Merge sort usa a recursividade em alguns

problemas e está técnica não é muito eficiente devido ao alto consumo de memória e

tempo de execução, mesmo tendo uma complexidade de tempo menor(Merge sort

Θ(n log2 n)) não significa que ele será mais eficiente que o Insertion sort que tem a

complexidade de tempo Θ (n2).

Um dos motivos para se preocupar com a melhor estrutura a ser utilizada em um

certo problema é que os computadores têm suas limitações, por mais que os

computadores atuais pareçam rápidos e sua memória seja absurdamente grande,

certas tarefas levam muito tempo para serem executadas, imagine um computador

que fosse infinitamente rápido, você não precisaria se preocupar com a estrutura que

escolheu para solucionar seu problema e assim todos os algoritmos capazes de

resolver uma tarefa teriam resultados iguais, assim utilizaríamos sempre o método

mais fácil de ser implementado, já que esse computador não existe e nunca vai

existir é de extrema importância criar algoritmos eficientes em termos de tempo e de

espaço alocado na memória para assim termos os melhores resultados possíveis.

5. Espaço de Complexidade de um Algoritmo

Existem dois tipos de utilização de espaço extra, o primeiro é quando os

elementos a serem ordenados excedem o tamanho da memória principal, e o segundo é

quando necessitamos de um espaço, como por exemplo, um vetor extra definido pelo

próprio algoritmo, para possibilitar a realização das operações.

  18  

No nosso caso, não foi utilizado o primeiro tipo (ordenação externa), e o segundo foi

utilizado paraos métodos de ordenação MergeSort e QuickSort.

6. Conclusão

De forma resumida, podemos concluir que, apesar de alguns algoritmos serem

mais eficientes que outros, em um caso especifico podemos mudar esta percepção, no

melhor caso, o BubbleSort tem um melhor desempenho que o QuickSort ou ShellSort. E o

ShellSort, ao observar o comportamento de tempo de execução, o ShellSort é o mais

eficiente.

A partir da análise matemática e empírica é possível analisar para qualquer caso o algoritmo

mais adequado. Após a conclusão deste relatório, seremos capazes de nos preocupar em

poupar memória, e fazer um algoritmo mais eficiente e cada vez mais profissional.

7. Referências Bibliográficas

1. SEDGEWICK, Robert, 1946 Algoriths in C / Robert Sedgewick – 3rd ed. – Reading,

Mass.: Addison Wesley, c1998.

2. TENEMBAUM, Aaron M., LAMNGSAM, Yedidyah, AUGENSTEIN, Mosha J.;

estruturas de dados Usando C, Pearson Makron Books, 2005.

3. ZIVIANI, Nívio, 2004 Projetos de Algoritmos.

4. QUEIROZ, Ana E., Notas de aula, 2009.