ED I - Aula 2 - Complexidade de Algoritmos

ED I - Aula 2 - Complexidade de Algoritmos

Prof. Manuel Fernandez Paradela Ledón

José Cassiano Grassi Gunji, [e-mail]​

• Impacto das comparações e de outras operações no desempenho do código;

• Análise assintótica, notação big-O, conceito de limite e de tamanho do problema.​

• Problemas e sua complexidade;

• Benchmarks;

• Contagem elementar de instruções;​

Complexidade de algoritmos

Estruturas de Dados I

Exercício ou problema?

Complexidade de Algoritmos

Demanda muito mais reflexão, pesquisa e esforço para desembaraçar antes de encontrar a abordagem apropriada.

​Problema

É uma questão que você sabe como resolver imediatamente. Você não precisa pesquisar quais técnicas utilizar para resolver o exercício.

​Exercício

​Desempenho e eficiência

• Completeza ou completude: o algoritmo oferece certeza de encontrar uma solução para o problema?

• Otimização: o algoritmo encontrará uma solução ótima para o problema (memória e espaço)?

• Complexidade de tempo: quanto tempo é necessário para se executar o algoritmo?

• Complexidade algorítmica: qual é o custo da implementação e manutenção dada sua complexidade?

Complexidade de Algoritmos

Lembrando...

Um pouco de matemática

​Polinômios

Revisão de Matemática

​Exemplos de polinômios com graus diferentes

Revisão de Matemática

​Exemplos de polinômios com graus diferentes

Revisão de Matemática

Funções Exponenciais

Revisão de Matemática

Funções Exponenciais

Revisão de Matemática

Comparação entre funções

Revisão de Matemática

​Gráficos para comparar o comportamento de algumas funções utilizando a ferramenta gratuita www.mathe-fa.de/pt

Multiple Choice

Se um algoritmo tiver sua complexidade definida, podemos dizer que:

• Ele sempre encontra uma solução

• Ele pode ser executado em um tempo aceitável

• Ele pode levar um tempo inaceitável para completar

• A complexidade é a solução do algoritmo

Complexidade de Algoritmos

Tratabilidade de algoritmos

Complexidade de Algoritmos

Um problema de complexidade exponencial (ou pior). Nenhum computador pode resolvê-lo em um tempo satisfatório, a não ser que o número n seja pequeno.

​Intratáveis

São problemas possivelmente resolvíveis com recursos limitados e em situações simples, porém impossíveis com recursos limitados e em situações reais mais complexas.

​Tratáveis

Problemas Tratáveis

Complexidade de Algoritmos

É uma classe de problemas resolvíveis em tempo polinomial em uma máquina não-determinística (máquina sem limites). NP significa nondeterministic polynomial time.

​Tipo NP

É uma classe de problemas resolvíveis em tempo polinomial em uma máquina determinística (máquina normal, limitada, um processo de cada vez)

​Tipo P

Computadores determinísticos e não-determinísticos

Complexidade de Algoritmos

Se a solução existe, o computador sempre a encontrará. Não existem limitações de hardware. É um computador paralelo que executa infinito número de processos simultaneamente.

Não-determinístico​

Só poderá estar em um estado por vez (PC comum, que executa um processo de cada vez).

Determinístico​

​Lenda do jogo de xadrez

Complexidade de Algoritmos

​https://ideiasesquecidas.com/2016/06/24/todos-os-graos-de-arroz-num-tabuleiro-de-xadrez/

​Um "boato" como função exponencial

Complexidade de Algoritmos

​Suponhamos que uma pessoa tem um grande segredo, mas no segundo dia não resiste mais e conta para outras três pessoas diferentes. Cada uma das três pessoas contará o segredo para outras três pessoas no dia seguinte.

Quantas pessoas saberão o "segredo" depois de uma semana?​

​Um "boato" como função exponencial

Complexidade de Algoritmos

​Um "boato" como função exponencial

Complexidade de Algoritmos

 E depois de 30 dias?

​Tempo em função do número de operações realizadas

Complexidade de Algoritmos

​Considerando um computador que realiza um milhão de operações por segundo.

Alguns algoritmos conhecidos e seu comportamento

Determinar qual o trabalhador com maior salário

Complexidade de Algoritmos

Ordenar alfabeticamente os trabalhadores, usando o método da bolha

Complexidade de Algoritmos

A Sequência de Fibonacci

Complexidade de Algoritmos

​0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

​Complexidade de algoritmos

Há várias maneiras de se avaliar a complexidade de um algoritmo. A maioria dos autores se concentram no consumo de memória e no tempo de execução.

Podemos medir a complexidade e a eficiência de um algoritmo efetuando:

• Contagem de instruções;

• Benchmark;

• Estimativa matemática.​

Complexidade de Algoritmos

​Benchmark

Complexidade de Algoritmos

​Contagem de instruções

Conta-se a quantidade de instruções para se resolver o problema. Entretanto, instruções diferentes levam tempos diferentes para serem executadas.

Por simplicidade, considera-se no cálculo de T(n) que todas as instruções rodam no mesmo tempo.​

Complexidade de Algoritmos

​Contagem de instruções - T(n) polinomial

int q = 0;

for (int i = 1; i <= n; i++){

q = q + 1;

}​

Complexidade de Algoritmos

​Contagem de instruções - T(n) logarítmico

int k = 0, i = n;

while (i > 1){

k = k + 1;

i = i / 2; //controle do laço​

}​

Complexidade de Algoritmos

​Notação big-O

• se f(x) é a soma de diferentes termos e existe um termo com a maior taxa de crescimento, este será considerado e os restantes omitidos;

• se f(x) é o produto de diferentes fatores, todas as constantes podem ser omitidas.

Complexidade de Algoritmos

​Notação big-O

Complexidade de Algoritmos

Multiple Choice

Seja $$f\left(n\right)=2n^4+2n^5+3n^2+12$$   a complexidade de um algoritmo, qual sua complexidade na notação big-O?

• $$O\left(2n^4\right)$$  

• $$O\left(n^4\right)$$  

• $$O\left(2n^5\right)$$  

• $$O\left(n^5\right)$$  

Multiple Choice

Seja $$f\left(n\right)=4n^5+3n^3+2^n+5$$   a complexidade de um algoritmo, qual sua complexidade na notação big-O?

• $$O\left(4n^5\right)$$  

• $$O\left(n^5\right)$$  

• $$O\left(2^n\right)$$  

• $$O\left(n^3\right)$$  

Homework

Resolva os 5 exercícios propostos no final da apresentação do prof. Ledón e poste suas respostas na tarefa do BlackBoard.

Complexidade de Algoritmos