Aula 3 - Complexidade de Algoritmos e Notação O

Prévia do material em texto

CCT0608 ALGORITMOS AVANÇADOS
Aula 3: Complexidade de Algoritmos e Notação O
Prof. Dr. Roney L. de S. Santos
RONEY.LIRASALE@professores.estacio.br
ALGORITMOS
2
ALGORITMOS
3
• Projetar algoritmos corretos
– Geram a solução esperada
• Eficientes
– Executam em tempo e espaço aceitáveis para problemas complexos
• Um algoritmo resolve um problema quando, para qualquer
entrada, produz uma resposta correta
– Se forem concedidos tempos e memória suficientes para sua execução
ALGORITMOS
4
• O fato de um algoritmo resolver (teoricamente) um problema
não significa que seja aceitável na prática
• Recursos de espaço e tempo requeridos têm grande importância
em casos práticos
• Às vezes, o algoritmo mais imediato está longe de ser razoável
em termos de eficiência
– Conseguem dar um exemplo?
ANÁLISE DE COMPLEXIDADE
5
• A complexidade = coração da Computação
– Surpresa? Algoritmos para problemas reais devem ser eficientes?
• Complexidade é uma técnica que faz-se necessária para torna-
la uma prática corriqueira no projeto de algoritmos
• Análise da complexidade é feita bem particular
– Parâmetros particulares do algoritmo
– Porém, ideias gerais que só dependem da estrutura do algoritmo
ANÁLISE DE COMPLEXIDADE
6
• Principais medidas de complexidade:
– Tempo
– Espaço
– Relação a velocidade e a quantidade de memória
• Formas de medir a complexidade: empírica
– Podemos pensar em medir experimentalmente a quantidade de trabalho
(tempo ou memória) requerida por um algoritmo executado em um
computador específico.
ANÁLISE DE COMPLEXIDADE
7
• Principais medidas de complexidade:
– Tempo
– Espaço
– Relação a velocidade e a quantidade de memória
• O esforço computacional de um algoritmo não pode ser descrito
simplesmente por um número
– Porque a quantidade de trabalho requerido depende da entrada
ANÁLISE DE COMPLEXIDADE
8
Quantidade de trabalho para executar um algoritmo
=
DESEMPENHO DO ALGORITMO
• Complexidade pessimista fornece o pior caso
– Máximo esforço
• Tempo requerido por um algoritmo sobre uma entrada pode ser
medido pelo número de execuções de algumas operações
ANÁLISE DE COMPLEXIDADE
9
• Tempo de Execução depende:
– Da implementação computacional
• Programa, linguagem, compilador
– Do ambiente de execução
• Processador
• Sistema operacional
• Memória (real e cache)
• Barramento...
– Organização e conteúdo dos dados de entrada
ANÁLISE DE COMPLEXIDADE
10
• Exemplo: buscar maior elemento em um vetor
– Pseudocódigo
ANÁLISE DE COMPLEXIDADE
11
• Deve-se identificar as operações primitivas e quantidade de
vezes que são executadas:
ANÁLISE DE COMPLEXIDADE
12
• Deve-se identificar as operações primitivas e quantidade de
vezes que são executadas:
NOTAÇÃO ASSINTÓTICA
13
• Usada para problemas realmente grandes
– Com entradas grandes
• Preocupação com o quão rápido os limites serão atingidos
– Ordem de Crescimento de Funções
– Pior caso
NOTAÇÃO ASSINTÓTICA
14
• Exemplos: o algoritmo A e B resolvem o mesmo problema.
• Complexidade de Tempo:
– A: 5000n | B: 1.1n
– Considere n = 10
– A requer 50000 passos | B requer 3
– Considere n = 1000
– A requer 5000000 passos | B requer 2,5 x 1041
• Para todos os casos, exceto n < 142, o tempo de A será menor
que o tempo de B!
FUNÇÕES TÍPICAS
15
FUNÇÕES TÍPICAS
16
ANÁLISE ASSINTÓTICA
17
• Observa a taxa de crescimento do tempo de execução
– Expressa por meio de uma função no tamanho da entrada
ANÁLISE ASSINTÓTICA
18
• A notação O define uma cota assintótica superior a menos de
constantes
• A função quadrática g(n) = n2 cresce mais rapidamente do que
a linear f(n) 7n + 13. Dizemos que a f(n) é O(g(n))
• Dizer que um algoritmo é O(1) significa que o número de
operações primitivas executadas é limitado por uma constante
– Analogamente, uma função O(n) é limitada superiormente por uma
função linear cn
ANÁLISE ASSINTÓTICA
19
ANÁLISE ASSINTÓTICA
20
ANÁLISE ASSINTÓTICA
21
ANÁLISE ASSINTÓTICA
22
ANÁLISE ASSINTÓTICA
23
ANÁLISE ASSINTÓTICA
24
ANÁLISE ASSINTÓTICA
25
GRUPO DA DISCIPLINA
26
• TELEGRAM: acesse o QR Code e entre no grupo!
• Principal meio de comunicação
• Informação sobre as aulas, provas,
cancelamentos, remarcações, alterações,
etc.
• Disponibilização do material da disciplina
• Caso queiram entrar em contato
diretamente comigo, basta mandar
mensagem no privado aqui pelo Telegram!
• Evitem o Whatsapp!
https://t.me/+tkY-3sVu6v0wNmYx
CCT0608 ALGORITMOS AVANÇADOS
27
• Dúvidas?
• Fiquem à vontade para entrar em contato no 
RONEY.LIRASALE@professores.estacio.br
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28