Análise de Algoritmos - Aula 01 (Guilherme)

Prévia do material em texto

Ana´lise de
Algoritmos
113859
Aula 1
Ana´lise de
Algoritmos
Bubble Sort
Merge Sort
NP-
Completude
Bem-vindo a` Ana´lise de Algoritmos
Ana´lise de
Algoritmos
113859
Aula 1
Ana´lise de
Algoritmos
Bubble Sort
Merge Sort
NP-
Completude
Bubble Sort
int v[N];
...
bubbleSort( int *v ){
int i,flag = 1;
while( flag ){
flag = 0;
for( i = 0; i < N-1; i++ )
if (v[i] > v[i+1]){ /* 1 comparac¸~ao */
swap( &v[i], &v[i+1] );
flag = 1;
}
}
}
Quantas comparac¸o˜es sera˜o feitas no pior caso?
Ana´lise de
Algoritmos
113859
Aula 1
Ana´lise de
Algoritmos
Bubble Sort
Merge Sort
NP-
Completude
Merge Sort
int v[N];
...
mergeSort( int *v, p, r ){
if ( p < r ) {
q = floor((p+r)/2);
mergeSort( v, p, q );
mergeSort( v, q+1, r );
merge( v, p, q, r ); /* r-p+1 comparac¸~oes */
}
}
Qual e´ o custo de mergeSort( v, 1, n )?
Ana´lise de
Algoritmos
113859
Aula 1
Ana´lise de
Algoritmos
Bubble Sort
Merge Sort
NP-
Completude
Por que estudar Induc¸a˜o?
Induc¸a˜o
Recursa˜o
Programac¸a˜o Dinaˆmica
⇓
Eficieˆncia
Ana´lise de
Algoritmos
113859
Aula 1
Ana´lise de
Algoritmos
NP-
Completude
NP-Completude
P1 Dado um conjunto C de n nu´meros inteiros, positivos ou
negativos, e um inteiro positivo s, decidir se existe um
subconjunto de C cuja soma de seus elementos e´ maior ou
igual a s.
• Exemplo: C = {−1,−7, 3, 11,−2, 0, 4,−8}; s = 16
Ana´lise de
Algoritmos
113859
Aula 1
Ana´lise de
Algoritmos
NP-
Completude
NP-Completude
P1 Dado um conjunto C de n nu´meros inteiros, positivos ou
negativos, e um inteiro positivo s, decidir se existe um
subconjunto de C cuja soma de seus elementos e´ maior ou
igual a s.
• Exemplo: C = {−1,−7, 3, 11,−2, 0, 4,−8}; s = 16
P2 Dado um conjunto C de n nu´meros inteiros, positivos ou
negativos, decidir se existe um subconjunto de C cuja
soma de seus elementos e´ zero.
• Exemplo: C = {−1,−7, 3, 11,−2, 5, 4,−8};
Ana´lise de
Algoritmos
113859
Aula 1
Ana´lise de
Algoritmos
NP-
Completude
NP-Completude
P1 esta´ na classe P
P2 esta´ na classe NP, mas
na˜o ha´ prova de que na˜o esteja em P
Por que os americanos esta˜o pagando US$ 1,000,000
para quem provar que P2 esta´ ou na˜o em P?
	Análise de Algoritmos
	Bubble Sort
	Merge Sort
	NP-Completude