Complexidade de Algoritmos, Notação assintótica, Algoritmos� polinomiais e intratáveis
jfrjunio
9,958 views
50 slides
Nov 17, 2014
Slide 1 of 50
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
About This Presentation
Complexidade de Algoritmos;Notação assintótica; Algoritmos �polinomiais e intratáveis
Slide Content
http://www.icmc.usp.br/pessoas/junio
Complexidade de Algoritmos:
Tempo e espaço; Notação
assintótica; Algoritmos
polinomiais e intratáveis
Professor: José Fernando Rodrigues Júnior
Universidade de São Paulo
Complexidade de Algoritmos:
Tempo e espaço; Notação
assintótica; Algoritmos
polinomiais e intratáveis
Professor: José Fernando Rodrigues Júnior
Universidade de São Paulo
http://www.icmc.usp.br/pessoas/junio
Introdução
Algoritmos e funções
Notação Assintótica – Interpretação
matemática
Notação Assintótica – Aplicação a algoritmos
Notação Assintótica – Interpretação
algorítmica
Notação Assintótica – Limitações
Notação Assintótica – Um indicador geral
Algoritmos Polinomiais e Exponenciais
Conclusões
Introdução
Algoritmos e funções
Notação Assintótica – Interpretação
matemática
Notação Assintótica – Aplicação a algoritmos
Notação Assintótica – Interpretação
algorítmica
Notação Assintótica – Limitações
Notação Assintótica – Um indicador geral
Algoritmos Polinomiais e Exponenciais
Conclusões
http://www.icmc.usp.br/pessoas/junio
Introdução
Porquê o estudo da Complexidade?
Escolher entre vários algoritmos o mais eficiente;
Desenvolver algoritmos mais eficientes;
Complexidade Computacional - torna possível
determinar se a definição de determinado algoritmo é
viável.
Introdução
Porquê o estudo da Complexidade?
Escolher entre vários algoritmos o mais eficiente;
Desenvolver algoritmos mais eficientes;
Complexidade Computacional - torna possível
determinar se a definição de determinado algoritmo é
viável.
http://www.icmc.usp.br/pessoas/junio
Algoritmos e Funções
Todo algoritmo define uma função matemática
f(n)= # de instruções
Ex.:
void Algoritmo1(int n){
int contador = 0;
for(int i = 0; I < n; I++){
contador++;
}
}
n passos para terminar
Algoritmos e Funções
Todo algoritmo define uma função matemática
f(n)= # de instruções
Ex.:
void Algoritmo1(int n){
int contador = 0;
for(int i = 0; I < n; I++){
contador++;
}
}
n passos para terminar
http://www.icmc.usp.br/pessoas/junio
Algoritmos e Funções
Todo algoritmo define uma função matemática
f(n)= # de instruções
Ex.:
void Algoritmo2(int n){
int contador = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
contador++;
}
}
}
n*n passos para terminar
Algoritmos e Funções
Todo algoritmo define uma função matemática
f(n)= # de instruções
Ex.:
void Algoritmo2(int n){
int contador = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
contador++;
}
}
}
n*n passos para terminar
http://www.icmc.usp.br/pessoas/junio
Algoritmos e Funções
Todo algoritmo define uma função matemática
f(n)= # de instruções
Ex.:
void Algoritmo3(int n){
int contador = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
for(int k = 0; k < n; k++){
contador++;
}
}
}
}
n*n*n passos para terminar
Algoritmos e Funções
Todo algoritmo define uma função matemática
f(n)= # de instruções
Ex.:
void Algoritmo3(int n){
int contador = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
for(int k = 0; k < n; k++){
contador++;
}
}
}
}
n*n*n passos para terminar
http://www.icmc.usp.br/pessoas/junio
Algoritmos e Funções
Algoritmo1Algoritmo2Algoritmo3
n = 1 1 1 1
n = 10 10 10
2
10
3
n = 100010
3
10
6
10
9
n = 10
6
10
6
10
12
10
18
f(n) = nf(n) = n
2
f(n) = n
3
Algoritmos e Funções
Algoritmo1Algoritmo2Algoritmo3
n = 1 1 1 1
n = 10 10 10
2
10
3
n = 100010
3
10
6
10
9
n = 10
6
10
6
10
12
10
18
f(n) = nf(n) = n
2
f(n) = n
3
http://www.icmc.usp.br/pessoas/junio
Algoritmos e Funções
Qual algoritmo você escolheria?
R.: basta olhar na função definida por cada
algoritmo
A função de um algoritmo melhor algoritmo para
um dado problema
Fatores: tempo de processamento, memória,
acessos a disco, largura de banda, entre outros
Algoritmos e Funções
Qual algoritmo você escolheria?
R.: basta olhar na função definida por cada
algoritmo
A função de um algoritmo melhor algoritmo para
um dado problema
Fatores: tempo de processamento, memória,
acessos a disco, largura de banda, entre outros
http://www.icmc.usp.br/pessoas/junio
Algoritmos e Funções
A prática de se reduzir um algoritmo a uma função
matemática denomina-se
“Análise de complexidade de algoritmos”
Algoritmos e Funções
A prática de se reduzir um algoritmo a uma função
matemática denomina-se
“Análise de complexidade de algoritmos”
http://www.icmc.usp.br/pessoas/junio
Algoritmos e Funções
Mas como se faz a análise de um algoritmo,
matematicamente falando?
R.: Notação Assintótica: como estabelecer uma
relação de ordem entre funções matemáticas?
Funções não são números!
Algoritmos e Funções
Mas como se faz a análise de um algoritmo,
matematicamente falando?
R.: Notação Assintótica: como estabelecer uma
relação de ordem entre funções matemáticas?
Funções não são números!
http://www.icmc.usp.br/pessoas/junio
Notação Assintótica – Interpretação
matemática
Caracterização de funções de 3 maneiras:
limites assintóticos superior, inferior e estrito
Notação Assintótica – Interpretação
matemática
Caracterização de funções de 3 maneiras:
limites assintóticos superior, inferior e estrito
http://www.icmc.usp.br/pessoas/junio
Notação Assintótica – Interpretação
matemática
1) Limite assintótico superior: O(g(n))
Uma função f(n) = O(g(n)), se f(n) ≤ c
1
*g(n) para uma
constante c
1
> 0 e para n ≥ n
0
n
0
Notação Assintótica – Interpretação
matemática
1) Limite assintótico superior: O(g(n))
Uma função f(n) = O(g(n)), se f(n) ≤ c
1
*g(n) para uma
constante c
1
> 0 e para n ≥ n
0
n
0
http://www.icmc.usp.br/pessoas/junio
Notação Assintótica – Interpretação
matemática
2) Limite assintótico inferior: W(g(n))
Uma função f(n) = W(g(n)), se f(n) ≥ c
1
*g(n) para uma
constante c
1
> 0 e para n ≥ n
0
Notação Assintótica – Interpretação
matemática
2) Limite assintótico inferior: W(g(n))
Uma função f(n) = W(g(n)), se f(n) ≥ c
1
*g(n) para uma
constante c
1
> 0 e para n ≥ n
0
http://www.icmc.usp.br/pessoas/junio
Notação Assintótica – Interpretação
matemática
3) Limite assintótico estrito: q(g(n))
Uma função f(n) = q(g(n)), se c
1
*g(n) ≤ f(n) ≤ c
2
*g(n)
para um constantes c
1 e
c
2
> 0 e para n ≥ n
0
Notação Assintótica – Interpretação
matemática
3) Limite assintótico estrito: q(g(n))
Uma função f(n) = q(g(n)), se c
1
*g(n) ≤ f(n) ≤ c
2
*g(n)
para um constantes c
1 e
c
2
> 0 e para n ≥ n
0
http://www.icmc.usp.br/pessoas/junio
Notação Assintótica – Interpretação
matemática
Principais limites assintóticos:
O(1) < O(logn) < O(n) < O(nlogn) < O(n
2
) < O(2
n
)
Notação Assintótica – Interpretação
matemática
Principais limites assintóticos:
O(1) < O(logn) < O(n) < O(nlogn) < O(n
2
) < O(2
n
)
http://www.icmc.usp.br/pessoas/junio
Notação Assintótica
Aplicação a algoritmos
Exemplo: suponha um algoritmo para calcular a
soma de uma seqüência de números
Notação Assintótica
Aplicação a algoritmos
Exemplo: suponha um algoritmo para calcular a
soma de uma seqüência de números
http://www.icmc.usp.br/pessoas/junio
Notação Assintótica
Aplicação a algoritmos
AlgForcaBruta(int n){
soma = 0
for(i = 1 to n)
soma = soma + i
}
1
n
n
Custo total: 1 + n + n = 2n + 1
f(n) = 2n + 1
Notação Assintótica
Aplicação a algoritmos
AlgForcaBruta(int n){
soma = 0
for(i = 1 to n)
soma = soma + i
}
1
n
n
Custo total: 1 + n + n = 2n + 1
f(n) = 2n + 1
http://www.icmc.usp.br/pessoas/junio
Notação Assintótica
Aplicação a algoritmos
AlgInstataneo(int n){
soma = n*(n+1)/2
}
4
Custo total: 4
f(n) = 4
Notação Assintótica
Aplicação a algoritmos
AlgInstataneo(int n){
soma = n*(n+1)/2
}
4
Custo total: 4
f(n) = 4
http://www.icmc.usp.br/pessoas/junio
Notação Assintótica
Aplicação a algoritmos
AlgBobo(int n){
soma = 0
for(i = 0 to n){
for(j = 1 to i){
soma = soma + 1
}
}
}
1
n
n((n+1)/2)
n((n+1)/2)
Custo total: 1 + n + n((n+1)/2) + n((n+1)/2)
f(n) = n
2
+ n +1
Notação Assintótica
Aplicação a algoritmos
AlgBobo(int n){
soma = 0
for(i = 0 to n){
for(j = 1 to i){
soma = soma + 1
}
}
}
1
n
n((n+1)/2)
n((n+1)/2)
Custo total: 1 + n + n((n+1)/2) + n((n+1)/2)
f(n) = n
2
+ n +1
http://www.icmc.usp.br/pessoas/junio
Notação Assintótica
Aplicação a algoritmos
O que temos então:
AlgForcaBruta: f(n) = 2n + 1
AlgInstantaneo: f(n) = 4
AlgBobo: f(n) = n
2
+ n +1
Notação Assintótica
Aplicação a algoritmos
O que temos então:
AlgForcaBruta: f(n) = 2n + 1
AlgInstantaneo: f(n) = 4
AlgBobo: f(n) = n
2
+ n +1
http://www.icmc.usp.br/pessoas/junio
Notação Assintótica
Aplicação a algoritmos
O AlgForcaBruta tem complexidade
f(n) = q(g(n))= q(n) , isto é, g(n) = n
Mas por quê, se f(n) = 2n + 1?
R.: segundo a definição de limite assintótico estrito
c1*g(n) ≤ f(n) ≤ c2*g(n) temos:
1*n ≤ f(n) = 2n + 1 ≤ 3*n
Notação Assintótica
Aplicação a algoritmos
O AlgForcaBruta tem complexidade
f(n) = q(g(n))= q(n) , isto é, g(n) = n
Mas por quê, se f(n) = 2n + 1?
R.: segundo a definição de limite assintótico estrito
c1*g(n) ≤ f(n) ≤ c2*g(n) temos:
1*n ≤ f(n) = 2n + 1 ≤ 3*n
http://www.icmc.usp.br/pessoas/junio
Notação Assintótica
Aplicação a algoritmos
O AlgInstantaneo tem complexidade
f(n) = q(g(n))= q(1) , isto é, g(n) = 1
Mas por quê, se f(n) = 4?
R.: segundo a definição de limite assintótico estrito
c1*g(n) ≤ f(n) ≤ c2*g(n) temos:
3*1 ≤ f(n) = 4 ≤ 5*1
Notação Assintótica
Aplicação a algoritmos
O AlgInstantaneo tem complexidade
f(n) = q(g(n))= q(1) , isto é, g(n) = 1
Mas por quê, se f(n) = 4?
R.: segundo a definição de limite assintótico estrito
c1*g(n) ≤ f(n) ≤ c2*g(n) temos:
3*1 ≤ f(n) = 4 ≤ 5*1
http://www.icmc.usp.br/pessoas/junio
Notação Assintótica
Aplicação a algoritmos
O AlgBobo tem complexidade
f(n) = q(g(n))= q(n
2
) , isto é, g(n) = n
2
Mas por quê, se f(n) = n
2
+ n + 1?
R.: segundo a definição de limite assintótico estrito
c1*g(n) ≤ f(n) ≤ c2*g(n) temos:
1* n
2
≤ f(n) = n
2
+ n + 1 ≤ 2* n
2
Notação Assintótica
Aplicação a algoritmos
O AlgBobo tem complexidade
f(n) = q(g(n))= q(n
2
) , isto é, g(n) = n
2
Mas por quê, se f(n) = n
2
+ n + 1?
R.: segundo a definição de limite assintótico estrito
c1*g(n) ≤ f(n) ≤ c2*g(n) temos:
1* n
2
≤ f(n) = n
2
+ n + 1 ≤ 2* n
2
http://www.icmc.usp.br/pessoas/junio
Notação Assintótica
Aplicação a algoritmos
O que temos então:
AlgForcaBruta: f(n) = 2n + 1 = q(n)
AlgInstantaneo: f(n) = 4 = q(1)
AlgBobo: f(n) = n
2
+ n +1 = q(n
2
)
Analisando-se o que a notação assintótica define,
verificam-se dois fatos:
Notação Assintótica
Aplicação a algoritmos
O que temos então:
AlgForcaBruta: f(n) = 2n + 1 = q(n)
AlgInstantaneo: f(n) = 4 = q(1)
AlgBobo: f(n) = n
2
+ n +1 = q(n
2
)
Analisando-se o que a notação assintótica define,
verificam-se dois fatos:
http://www.icmc.usp.br/pessoas/junio
Notação Assintótica
Aplicação a algoritmos
Analisando-se o que a notação assintótica define,
verificam-se dois fatos:
1) A notação assintótica não está interessada na
função específica f(n), mas na sua taxa de
crescimento com relação a n. As constantes da
função f(n) são ignoradas.
2) Os termos de mais baixa ordem são ignorados.
Notação Assintótica
Aplicação a algoritmos
Analisando-se o que a notação assintótica define,
verificam-se dois fatos:
1) A notação assintótica não está interessada na
função específica f(n), mas na sua taxa de
crescimento com relação a n. As constantes da
função f(n) são ignoradas.
2) Os termos de mais baixa ordem são ignorados.
http://www.icmc.usp.br/pessoas/junio
Notação Assintótica
Aplicação a algoritmos
Mas por quê os termos de mais baixa ordem são
ignorados?
R.: a notação considera valores de n arbitrariamente
grandes. Se f(n) < h(n), então
f(n)
h(n)
lim
n¥
= 0
Ex.: f(n) = n
2
> h(n) = n
para n = 10
10
, temos n = 10
10
= 0
n
2
10
100
~
Notação Assintótica
Aplicação a algoritmos
Mas por quê os termos de mais baixa ordem são
ignorados?
R.: a notação considera valores de n arbitrariamente
grandes. Se f(n) < h(n), então
f(n)
h(n)
lim
n¥
= 0
Ex.: f(n) = n
2
> h(n) = n
para n = 10
10
, temos n = 10
10
= 0
n
2
10
100
~
http://www.icmc.usp.br/pessoas/junio
Notação Assintótica
Interpretação algorítmica
Os limites assintóticos têm a seguinte interpretação
com relação a algoritmos.
Dado um algoritmo com função f(n)...
Notação Assintótica
Interpretação algorítmica
Os limites assintóticos têm a seguinte interpretação
com relação a algoritmos.
Dado um algoritmo com função f(n)...
http://www.icmc.usp.br/pessoas/junio
Notação Assintótica
Interpretação algorítmica
• Limite assintótico superior: O(g(n))
Indica que não importam quais as circunstâncias,
f(n) ≤ g(n) sempre
“g(n) é o pior que o meu algoritmo pode fazer”
Notação Assintótica
Interpretação algorítmica
• Limite assintótico superior: O(g(n))
Indica que não importam quais as circunstâncias,
f(n) ≤ g(n) sempre
“g(n) é o pior que o meu algoritmo pode fazer”
http://www.icmc.usp.br/pessoas/junio
Notação Assintótica
Interpretação algorítmica
Exemplo: algoritmo de ordenação Quicksort
Possíveis circunstâncias:
1)ordenar uma seqüência que já está em ordem
o Quicksort tem custo n
2
2) ordenar uma seqüência totalmente embaralhada
o Quicksort tem custo n*logn
como n
2
é o pior que o Quicksort pode fazer, ele
terá sempre
f(n) ≤ n
2
O(n
2
)
Notação Assintótica
Interpretação algorítmica
Exemplo: algoritmo de ordenação Quicksort
Possíveis circunstâncias:
1)ordenar uma seqüência que já está em ordem
o Quicksort tem custo n
2
2) ordenar uma seqüência totalmente embaralhada
o Quicksort tem custo n*logn
como n
2
é o pior que o Quicksort pode fazer, ele
terá sempre
f(n) ≤ n
2
O(n
2
)
http://www.icmc.usp.br/pessoas/junio
Notação Assintótica
Interpretação algorítmica
• Limite assintótico inferior: W(g(n))
Indica que não importam quais as circunstâncias,
f(n) ≥ g(n) sempre
“g(n) é o melhor que o meu algoritmo pode fazer”
Notação Assintótica
Interpretação algorítmica
• Limite assintótico inferior: W(g(n))
Indica que não importam quais as circunstâncias,
f(n) ≥ g(n) sempre
“g(n) é o melhor que o meu algoritmo pode fazer”
http://www.icmc.usp.br/pessoas/junio
Notação Assintótica
Interpretação algorítmica
Exemplo: algoritmo de ordenação Quicksort
Possíveis circunstâncias:
1)ordenar uma seqüência que já está em ordem
o Quicksort demora n
2
2) ordenar uma seqüência totalmente embaralhada
o Quicksort demora n*logn
como n*logn é o melhor que o Quicksort pode
fazer, ele terá sempre
f(n) ≥ n*logn W(n*logn)
Notação Assintótica
Interpretação algorítmica
Exemplo: algoritmo de ordenação Quicksort
Possíveis circunstâncias:
1)ordenar uma seqüência que já está em ordem
o Quicksort demora n
2
2) ordenar uma seqüência totalmente embaralhada
o Quicksort demora n*logn
como n*logn é o melhor que o Quicksort pode
fazer, ele terá sempre
f(n) ≥ n*logn W(n*logn)
http://www.icmc.usp.br/pessoas/junio
Notação Assintótica
Interpretação algorítmica
• Limite assintótico estrito: q(g(n))
Indica que não importam quais as circunstâncias,
c
1
g(n) ≤ f(n) ≤ c2g(n) sempre
“meu algoritmo não faz nem pior, nem melhor
que g(n)”
Notação Assintótica
Interpretação algorítmica
• Limite assintótico estrito: q(g(n))
Indica que não importam quais as circunstâncias,
c
1
g(n) ≤ f(n) ≤ c2g(n) sempre
“meu algoritmo não faz nem pior, nem melhor
que g(n)”
http://www.icmc.usp.br/pessoas/junio
Notação Assintótica
Interpretação algorítmica
Exemplo: algoritmo de ordenação Heapsort
Possíveis circunstâncias:
1)seqüência já ordenada custo n*logn
2) seqüência em ordem inversa custo n*logn
3) seqüência totalmente embaralhada custo n*logn
em todos os casos n*logn é sempre o que o meu
algoritmo faz
c1n*logn ≤ f(n) ≤ c2n*logn q(n*logn)
Notação Assintótica
Interpretação algorítmica
Exemplo: algoritmo de ordenação Heapsort
Possíveis circunstâncias:
1)seqüência já ordenada custo n*logn
2) seqüência em ordem inversa custo n*logn
3) seqüência totalmente embaralhada custo n*logn
em todos os casos n*logn é sempre o que o meu
algoritmo faz
c1n*logn ≤ f(n) ≤ c2n*logn q(n*logn)
http://www.icmc.usp.br/pessoas/junio
Notação Assintótica
Interpretação algorítmica
•Pior caso, melhor caso e caso médio
Exemplo: algoritmo de ordenação Insertion-sort
Possíveis circunstâncias
1)seqüência já ordenada custo n
2)seqüência em ordem inversa custo n
2
3)seqüência toda embaralhada custo n + d, tal
que d é o número de operações de rearranjo
Notação Assintótica
Interpretação algorítmica
•Pior caso, melhor caso e caso médio
Exemplo: algoritmo de ordenação Insertion-sort
Possíveis circunstâncias
1)seqüência já ordenada custo n
2)seqüência em ordem inversa custo n
2
3)seqüência toda embaralhada custo n + d, tal
que d é o número de operações de rearranjo
http://www.icmc.usp.br/pessoas/junio
Notação Assintótica
Interpretação algorítmica
•Para o Insertion-sort valem as seguintes afirmações:
•ele é, ao mesmo tempo, O(n
2
) e W(n)
•considerando-se apenas as melhores entradas,
pode-se dizer:
“q(n) no melhor caso”
•considerando-se apenas as piores entradas, pode-
se dizer:
“q(n
2
) no pior caso”
•considerando-se apenas as demais entradas, que
são a maioria mais provável, pode-se dizer:
“q(n + d) no caso médio”
Notação Assintótica
Interpretação algorítmica
•Para o Insertion-sort valem as seguintes afirmações:
•ele é, ao mesmo tempo, O(n
2
) e W(n)
•considerando-se apenas as melhores entradas,
pode-se dizer:
“q(n) no melhor caso”
•considerando-se apenas as piores entradas, pode-
se dizer:
“q(n
2
) no pior caso”
•considerando-se apenas as demais entradas, que
são a maioria mais provável, pode-se dizer:
“q(n + d) no caso médio”
http://www.icmc.usp.br/pessoas/junio
Notação Assintótica
Interpretação algorítmica
•Para o Insertion-sort valem as seguintes afirmações:
•ele é, ao mesmo tempo, O(n
2
) e W(n)
1)já ordenada custo n
2)em ordem inversa custo n
2
3)toda embaralhada custo n + d
Notação Assintótica
Interpretação algorítmica
•Para o Insertion-sort valem as seguintes afirmações:
•ele é, ao mesmo tempo, O(n
2
) e W(n)
1)já ordenada custo n
2)em ordem inversa custo n
2
3)toda embaralhada custo n + d
http://www.icmc.usp.br/pessoas/junio
Notação Assintótica
Interpretação algorítmica
•Para o Insertion-sort valem as seguintes afirmações:
•ele é, ao mesmo tempo, O(n
2
) e W(n)
•considerando-se apenas as melhores entradas,
pode-se dizer:
“q(n) no melhor caso”
•considerando-se apenas as piores entradas, pode-
se dizer:
“q(n
2
) no pior caso”
•considerando-se apenas as demais entradas, que
são a maioria mais provável, pode-se dizer:
“q(n + d) no caso médio”
1)já ordenada custo n
2)em ordem inversa custo n
2
3)toda embaralhada custo n + d
Notação Assintótica
Interpretação algorítmica
•Para o Insertion-sort valem as seguintes afirmações:
•ele é, ao mesmo tempo, O(n
2
) e W(n)
•considerando-se apenas as melhores entradas,
pode-se dizer:
“q(n) no melhor caso”
•considerando-se apenas as piores entradas, pode-
se dizer:
“q(n
2
) no pior caso”
•considerando-se apenas as demais entradas, que
são a maioria mais provável, pode-se dizer:
“q(n + d) no caso médio”
1)já ordenada custo n
2)em ordem inversa custo n
2
3)toda embaralhada custo n + d
http://www.icmc.usp.br/pessoas/junio
Notação Assintótica
Interpretação algorítmica
•Para o Insertion-sort valem as seguintes afirmações:
•ele é, ao mesmo tempo, O(n
2
) e W(n)
•considerando-se apenas as melhores entradas,
pode-se dizer:
“q(n) no melhor caso”
•considerando-se apenas as piores entradas, pode-
se dizer:
“q(n
2
) no pior caso”
•considerando-se apenas as demais entradas, que
são a maioria mais provável, pode-se dizer:
“q(n + d) no caso médio”
1)já ordenada custo n
2)em ordem inversa custo n
2
3)toda embaralhada custo n + d
Notação Assintótica
Interpretação algorítmica
•Para o Insertion-sort valem as seguintes afirmações:
•ele é, ao mesmo tempo, O(n
2
) e W(n)
•considerando-se apenas as melhores entradas,
pode-se dizer:
“q(n) no melhor caso”
•considerando-se apenas as piores entradas, pode-
se dizer:
“q(n
2
) no pior caso”
•considerando-se apenas as demais entradas, que
são a maioria mais provável, pode-se dizer:
“q(n + d) no caso médio”
1)já ordenada custo n
2)em ordem inversa custo n
2
3)toda embaralhada custo n + d
http://www.icmc.usp.br/pessoas/junio
Notação Assintótica
Interpretação algorítmica
•Para o Insertion-sort valem as seguintes afirmações:
•ele é, ao mesmo tempo, O(n
2
) e W(n)
•considerando-se apenas as melhores entradas,
pode-se dizer:
“q(n) no melhor caso”
•considerando-se apenas as piores entradas, pode-
se dizer:
“q(n
2
) no pior caso”
•considerando-se apenas as demais entradas, que
são a maioria mais provável, pode-se dizer:
“q(n + d) no caso médio”
1)já ordenada custo n
2)em ordem inversa custo n
2
3)toda embaralhada custo n + d
Notação Assintótica
Interpretação algorítmica
•Para o Insertion-sort valem as seguintes afirmações:
•ele é, ao mesmo tempo, O(n
2
) e W(n)
•considerando-se apenas as melhores entradas,
pode-se dizer:
“q(n) no melhor caso”
•considerando-se apenas as piores entradas, pode-
se dizer:
“q(n
2
) no pior caso”
•considerando-se apenas as demais entradas, que
são a maioria mais provável, pode-se dizer:
“q(n + d) no caso médio”
1)já ordenada custo n
2)em ordem inversa custo n
2
3)toda embaralhada custo n + d
http://www.icmc.usp.br/pessoas/junio
Notação Assintótica
Interpretação algorítmica
•Para o Insertion-sort valem as seguintes afirmações:
•ele é, ao mesmo tempo, O(n
2
) e W(n)
•considerando-se apenas as melhores entradas,
pode-se dizer:
“q(n) no melhor caso”
•considerando-se apenas as piores entradas, pode-
se dizer:
“q(n
2
) no pior caso”
•considerando-se apenas as demais entradas, que
são a maioria mais provável, pode-se dizer:
“q(n + d) no caso médio”
Notação Assintótica
Interpretação algorítmica
•Para o Insertion-sort valem as seguintes afirmações:
•ele é, ao mesmo tempo, O(n
2
) e W(n)
•considerando-se apenas as melhores entradas,
pode-se dizer:
“q(n) no melhor caso”
•considerando-se apenas as piores entradas, pode-
se dizer:
“q(n
2
) no pior caso”
•considerando-se apenas as demais entradas, que
são a maioria mais provável, pode-se dizer:
“q(n + d) no caso médio”
http://www.icmc.usp.br/pessoas/junio
Notação Assintótica
Interpretação algorítmica
•Para o Insertion-sort valem as seguintes afirmações:
•ele é, ao mesmo tempo, O(n
2
) e W(n)
•considerando-se apenas as melhores entradas,
pode-se dizer:
“q(n) no melhor caso”
•considerando-se apenas as piores entradas, pode-
se dizer:
“q(n
2
) no pior caso”
•considerando-se apenas as demais entradas, que
são a maioria mais provável, pode-se dizer:
“q(n + d) no caso médio”
Notação Assintótica
Interpretação algorítmica
•Para o Insertion-sort valem as seguintes afirmações:
•ele é, ao mesmo tempo, O(n
2
) e W(n)
•considerando-se apenas as melhores entradas,
pode-se dizer:
“q(n) no melhor caso”
•considerando-se apenas as piores entradas, pode-
se dizer:
“q(n
2
) no pior caso”
•considerando-se apenas as demais entradas, que
são a maioria mais provável, pode-se dizer:
“q(n + d) no caso médio”
http://www.icmc.usp.br/pessoas/junio
Notação Assintótica
Interpretação algorítmica
•Para o Insertion-sort valem as seguintes afirmações:
•ele é, ao mesmo tempo, O(n
2
) e W(n)
•considerando-se apenas as melhores entradas,
pode-se dizer:
“q(n) no melhor caso”
•considerando-se apenas as piores entradas, pode-
se dizer:
“q(n
2
) no pior caso”
•considerando-se apenas as demais entradas, que
são a maioria mais provável, pode-se dizer:
“q(n + d) no caso médio”
Intuição geral:
• quando se diz:
“um algoritmo tem complexidade x”
isso é válido para TODAS as entradas
• quando se diz:
“um algoritmo tem complexidade x em tal caso”
isso é válido para TODAS as entradas que constituem
aquele caso
Notação Assintótica
Interpretação algorítmica
•Para o Insertion-sort valem as seguintes afirmações:
•ele é, ao mesmo tempo, O(n
2
) e W(n)
•considerando-se apenas as melhores entradas,
pode-se dizer:
“q(n) no melhor caso”
•considerando-se apenas as piores entradas, pode-
se dizer:
“q(n
2
) no pior caso”
•considerando-se apenas as demais entradas, que
são a maioria mais provável, pode-se dizer:
“q(n + d) no caso médio”
Intuição geral:
• quando se diz:
“um algoritmo tem complexidade x”
isso é válido para TODAS as entradas
• quando se diz:
“um algoritmo tem complexidade x em tal caso”
isso é válido para TODAS as entradas que constituem
aquele caso
http://www.icmc.usp.br/pessoas/junio
Notação Assintótica
Limitações
•Como se pode ver, a notação assintótica tem
expressividade limitada
1)por si só, ela não apresenta dados a respeito da
qualidade da entrada
2)a notação oculta fatores importantes que podem
fazer diferença na escolha de um algoritmo
Por exemplo:
se um algoritmo tem complexidade n
2
= q(n
2
)
e outro algoritmo tem complexidade 100n = q(n)
entradas de tamanho até 100, é melhor usar o
primeiro algoritmo, pois n
2
≤ 100n, para n ≤ 100
Notação Assintótica
Limitações
•Como se pode ver, a notação assintótica tem
expressividade limitada
1)por si só, ela não apresenta dados a respeito da
qualidade da entrada
2)a notação oculta fatores importantes que podem
fazer diferença na escolha de um algoritmo
Por exemplo:
se um algoritmo tem complexidade n
2
= q(n
2
)
e outro algoritmo tem complexidade 100n = q(n)
entradas de tamanho até 100, é melhor usar o
primeiro algoritmo, pois n
2
≤ 100n, para n ≤ 100
http://www.icmc.usp.br/pessoas/junio
Notação Assintótica
Limitações
•Como se pode ver, a notação assintótica tem
expressividade limitada
1)por si só, ela não apresenta dados a respeito da
qualidade da entrada
2)a notação oculta fatores importantes que podem
fazer diferença na escolha de um algoritmo
Por exemplo:
se um algoritmo tem complexidade n
2
= q(n
2
)
e outro algoritmo tem complexidade 100n = q(n)
entradas de tamanho até 100, é melhor usar o
primeiro algoritmo, pois n
2
≤ 100n, para n ≤ 100
Notação Assintótica
Limitações
•Como se pode ver, a notação assintótica tem
expressividade limitada
1)por si só, ela não apresenta dados a respeito da
qualidade da entrada
2)a notação oculta fatores importantes que podem
fazer diferença na escolha de um algoritmo
Por exemplo:
se um algoritmo tem complexidade n
2
= q(n
2
)
e outro algoritmo tem complexidade 100n = q(n)
entradas de tamanho até 100, é melhor usar o
primeiro algoritmo, pois n
2
≤ 100n, para n ≤ 100
http://www.icmc.usp.br/pessoas/junio
Notação Assintótica
Limitações
•Como se pode ver, a notação assintótica tem
expressividade limitada
1)por si só, ela não apresenta dados a respeito da
qualidade da entrada
2)a notação oculta fatores importantes que podem
fazer diferença na escolha de um algoritmo
Por exemplo:
se um algoritmo tem complexidade n
2
= q(n
2
)
e outro algoritmo tem complexidade 100n = q(n)
entradas de tamanho até 100, é melhor usar o
primeiro algoritmo, pois n
2
≤ 100n, para n ≤ 100
Notação Assintótica
Limitações
•Como se pode ver, a notação assintótica tem
expressividade limitada
1)por si só, ela não apresenta dados a respeito da
qualidade da entrada
2)a notação oculta fatores importantes que podem
fazer diferença na escolha de um algoritmo
Por exemplo:
se um algoritmo tem complexidade n
2
= q(n
2
)
e outro algoritmo tem complexidade 100n = q(n)
entradas de tamanho até 100, é melhor usar o
primeiro algoritmo, pois n
2
≤ 100n, para n ≤ 100
http://www.icmc.usp.br/pessoas/junio
Notação Assintótica
Limitações
•Como se pode ver, a notação assintótica tem
expressividade limitada
1)por si só, ela não apresenta dados a respeito da
qualidade da entrada
2)a notação oculta fatores importantes que podem
fazer diferença na escolha de um algoritmo
Por exemplo:
se um algoritmo tem complexidade n
2
= q(n
2
)
e outro algoritmo tem complexidade 100n = q(n)
entradas de tamanho até 100, é melhor usar o
primeiro algoritmo, pois n
2
≤ 100n, para n ≤ 100
É preciso conhecer bem o problema que se
tem, para que se possa fazer uma boa
escolha.
Notação Assintótica
Limitações
•Como se pode ver, a notação assintótica tem
expressividade limitada
1)por si só, ela não apresenta dados a respeito da
qualidade da entrada
2)a notação oculta fatores importantes que podem
fazer diferença na escolha de um algoritmo
Por exemplo:
se um algoritmo tem complexidade n
2
= q(n
2
)
e outro algoritmo tem complexidade 100n = q(n)
entradas de tamanho até 100, é melhor usar o
primeiro algoritmo, pois n
2
≤ 100n, para n ≤ 100
É preciso conhecer bem o problema que se
tem, para que se possa fazer uma boa
escolha.
http://www.icmc.usp.br/pessoas/junio
Notação Assintótica
Um indicador geral
•Usada para indicar os requisitos de qualquer fator
que creça como uma função de n. Os principais
são:
•tempo, como já visto
•o espaço de memória
•o número de acessos a disco
•a largura de banda
Notação Assintótica
Um indicador geral
•Usada para indicar os requisitos de qualquer fator
que creça como uma função de n. Os principais
são:
•tempo, como já visto
•o espaço de memória
•o número de acessos a disco
•a largura de banda
http://www.icmc.usp.br/pessoas/junio
Algoritmos Polinomiais e
Exponenciais
Algoritmos Polinomiais e
Exponenciais
http://www.icmc.usp.br/pessoas/junio
Algoritmos Polinomiais e
Exponenciais
Suponha-se um algoritmo com ordem O(2
n
)
para n = 100
um computador que realiza 2
12
operações/segundo
tempo total: 4*10
10
anos!!!
Algoritmos Polinomiais e
Exponenciais
Suponha-se um algoritmo com ordem O(2
n
)
para n = 100
um computador que realiza 2
12
operações/segundo
tempo total: 4*10
10
anos!!!
http://www.icmc.usp.br/pessoas/junio
Conclusões
•A análise de complexidade depende da
compreensão de dois fatores:
•interpretação matemática
•interpretação algorítmica
•Deve-se sempre lembrar que existem outras
dimensões envolvidas na análise, como qualidade
da entrada e arquitetura computacional
•A análise assintótica fornece um bom parâmetro,
mas não deve ser o único a ser considerado
Conclusões
•A análise de complexidade depende da
compreensão de dois fatores:
•interpretação matemática
•interpretação algorítmica
•Deve-se sempre lembrar que existem outras
dimensões envolvidas na análise, como qualidade
da entrada e arquitetura computacional
•A análise assintótica fornece um bom parâmetro,
mas não deve ser o único a ser considerado
Categories
TechnologyDownload
Download Slideshow Get the original presentation fileQuick Actions
Statistics
- Views 9,958
- Slides 50
- Favorites 11
- Age 4034 days
Related Slideshows
11
8-top-ai-courses-for-customer-support-representatives-in-2025.pptx
JeroenErne2
48 views
10
7-essential-ai-courses-for-call-center-supervisors-in-2025.pptx
JeroenErne2
47 views
13
25-essential-ai-courses-for-user-support-specialists-in-2025.pptx
JeroenErne2
37 views
11
8-essential-ai-courses-for-insurance-customer-service-representatives-in-2025.pptx
JeroenErne2
34 views
21
Know for Certain
DaveSinNM
22 views
17
PPT OPD LES 3ertt4t4tqqqe23e3e3rq2qq232.pptx
novasedanayoga46
26 views