ANÁLISE DE ALGORITMOS

Análise de algoritmos

Roberto Aragy

- Objetivo: analisar os principais algoritmos, definir qual a melhor forma de realizar a tarefa almejada, conhecer o desempenho dos principais algoritmos

- Algoritmos

→ métodos de provas

- indução matemática

→ complexidade

- funções de crescimento

- O, Ohmega, Theta

→ análise de algoritmos classicos

- ordenação

- busca

→ técnicas

- metodos gulosos

- divisao e conquista

- programação dinamica

- força bruta/backtracking

- recorrencia

Trabalho do bimestre

- Implementação/pesquisa de algoritmos de ordenação e busca

Ordenação bolha - Bubblesort

Ordenação por inserção – Insertsort

Ordenação por seleção – Selectsort

Mergesort

Quicksort

Heapsort

Ordenação por contagem

Busca sequencial

Busca binária

Em linguagem C

- Realizar experimentação e analises nestes algoritmos

Sugestão de pesquisa - RosettaStone

Algoritmo

- Ele deve fazer o que se espera - “Corretude”

- O algoritmo resolve o problema em tempo hábil

- O algoritmo consegue resolver o problema computacional utilizando os recursos do sistema de forma otimizada

Algoritmo – sequencia ordenada de instruções a serem seguidas, com o intuito de resolver um problema

Problema computacional – um problema a ser resolvido por um computador

A capacidade de um computador abstrair uma situação problema para realizar uma operação para o usuário.

Ex: o problema da ordenação → dada uma sequência de números, a saida do algoritmo deve retornar essas sequencia de modo ordenado.

Exemplos de problemas computacionais:

- Projeto genoma humano

- Internet

- Comércio eletrônico

- Alocação de recursos

Ex: Alocação de recursos → salas para realização de palestras – o sistema deve ser capaz de organizar as salas para atender à demanda de palestras, de acordo com o número de participantes.

Análise – comparação entre algoritmos com relação a uma previsão de tempo de execução

O tempo é computado de acordo com a quantidade de operações a serem executadas

- Daonde vem esta estimativa?

BuscaSequencial (A,x,n){

        Para i de 1 ate n faça

                Se A[i] = x

                        Retorna i

                Fimse

        Fimpara

Retorna -1

}

Operações básicas de um algoritmo

- Atribuição de valor

- Operação aritmética

- Operação lógica

- Operação comparativa

- Busca de endereçamento (Ex: busca em uma matriz, vetor)

Em um array, o endereço de memoria referenciado pelo nome da variável A é o da posição A[0]. Para achar os demais elementos do array, deve-se realizar uma busca de endereçamento a partir dele.

- Salto de endereço (Ex: loop, goto, break)

- Chamada de função

- Retorno de função

Tempo de execução: marcar cada linha em que haja uma ou mais operações básicas.

Exemplo de contagem de operações:

1-        Para i de 1 ate n faça

- i <- 1 → atribuição (na primeira execução)

- i <= n → comparação (realizado n + 1 vezes)

2-                Se A[i] = x

- A [ ] → endereçamento de array

- A [i] == x → comparação (realizado n vezes)

3-                        Retorna i

- Retorno de função, caso Se for Verdadeiro

- Na pior possibilidade: não executada

Pior possibilidade = x é diferente de todos os elementos do array A[].

4-                Fimse

5-        Fimpara

- i++ → incrementação de indice (realizado n vezes)

6- Retorna -1

- Retorno de função

- Na pior possibilidade: executada 1 vez

Número máximo aproximado de operações, na pior possibilidade:

1 + (n+1) + (n) + (n) + 1

F (n) = 3n + 3

A pior possibilidade é considerada a situação em que será utilizado o maior tempo de execução.

Ex

Ordenação bolha Naive (A, n)

1-         Para i de 1 ate n-1 faça

2-                 Para j de 1 ate n faça

3-                         Se A [j] > A[j+1]

4-                                 temp ← A[j]

5-                                 A [j] ← A [j+1]

6-                                 A [j+1] ← temp

7-                         Fimse

8-                 Fimpara

9-         Fimpara