AEDSII_aula_010_exercicios_complexidade

Prévia do material em texto

Complexidade	
  de	
  algoritmos	
  
Exemplos	
  e	
  exercícios	
  
Exemplo	
  1	
  
int find ( int a[], int n, int x ) 
{ 
 int i; 
 for ( i = 0; i < n; i++ ) 
 { 
 if ( a[i] == x ) 
 return i; 
 } 
 return 0; 
} 
Exemplo	
  2	
  
int find ( int a[], int n, int x ) 
{ 
 int i = 0, mid; 
 while ( i < n ) { 
 mid = ( n + i ) / 2; 
 if ( a[mid] < x ) 
 n = mid; 
 else if ( a[mid] > x ) 
 i = mid + 1; 
 else return mid; 
 } 
 return 0; 
} 
Exemplo	
  3	
  
void bubbleSort(int *array, int size) 
{ 
 int swapped = 0; 
 int x; 
 do { 
 swapped = 0; 
 for (x = 0; x < size-1;x++) { 
 if (array[x]>array[x+1]) { 
 swap(&array[x], &array[x+1]); 
 swapped = 1; 
 } 
 } 
 } while (swapped); 
} 
Exemplo	
  4	
  
void insert(int *array, int pos, int value) 
{ 
 pos--; 
 while (pos >= 0 && array[pos] > value) { 
 array[pos+1] = array[pos]; 
 pos--; 
 } 
 array[pos+1] = value; 
} 
 
void insertionSort(int *array, int size) 
{ 
 int x; 
 for (x = 0; x < size; x++) { 
 insert(array, x, array[x]); 
 } 
} 
Exemplo	
  5	
  
int Exemplo5(int N, int M) { 
int result=0, x=0, i, j, k; 
 
for (i = 0; i < N; i++) 
 for (j = i; j < N; j++) { 
 for (k = 0; k < M; k++) { 
 x=0; 
 while (x<N) { 
 result++; 
 x+=3; 
 } 
 } 
 for (k = 0; k < 2*M; k++) 
 if (k % 7 == 4) result++; 
 } 
return result; 
} 
Exemplo	
  6	
  
#define X 0 
#define Y 1 
int Area2(Point a, b, c) { 
 return (a[X]*b[Y] – a[Y]*b[X] 
 + a[Y]*c[X] – a[X]*c[Y] 
 + b[X]*c[Y] - c[X]*b[Y]); 
} 
 
int AreaPoligono2(Polygon P) { 
int i, sum = 0; 
 
for (i = 1; i < P.numvertices - 1; i++) 
 sum += Area2(P[0], P[i], P[i+1]); 
 
return sum; 
} 
Exemplo	
  7	
  #define MAX 1000 
int Escolhe(int k); // funcao com custo O(n^2) 
int Transfere(int k); // funcao com custo O(log n) 
 
void main() { 
int i, n, sum = 0; 
int vetor[MAX]; 
scanf(“%d”, &n); 
 
for (i = 0; i < n; i++) 
 vetor[i] = rand() % 50; // inteiro entre 0 e 49 
 
for (i = 0; i < n; i++) { 
 for (j = 0; j < vetor[i]; j++) { 
 if (vetor[j] < vetor[i]) 
 vetor[j] = Escolhe(vetor[i]); 
 else 
 vetor[j] = vetor[i]; 
 } 
 
 k = vetor[i]; 
 while (k > 0) { 
 Transfere(vetor[k]); 
 k--; 
 } 
} 
} 
	
  
Algoritmos e Estrutura de Dados II 
Teorema Mestre 
T(n) = 2T(n/2) + n; 
T(1) = 1; 
)).(()( temos 
,1 para )()/( se e 0 para )()( Se 3.
).log()( temos 
,)()( Se 2.
).()( temos 
,0 com ,)()( Se 1.
log
log
log
log
log
nfnT
cncfbnafnnf
nnnT
nnf
nnT
nOnf
a
a
a
a
a
b
b
b
b
b
Θ=
<≤>Ω=
Θ=
Θ=
Θ=
>=
+
−
ε
ε
ε
ε
)()/()( nfbnaTnT +=
•  g(n) é O(f(n)): g(n) ≤ cf(n), para todo n ≥ m 
•  g(n) é Ω(f(n)): g(n) ≥ cf(n), para todo n ≥ m 
•  g(n) é Ө(f(n)): 0 ≤ c1f(n) ≤ g(n) ≤ c2f(n), para todo n ≥ m 
Algoritmos e Estrutura de Dados II 
Ex. 1 
T(n) = 2T(n/2) + n; 
T(1) = 1; 
int main() { 
 int i, ia, ib, x, n; 
 int A[10]={ . . . }; 
 int B[10]={ . . . }; 
 A[11] = -∞; 
 B[11] = -∞; 
 cout<<"\nEntre com o valor de n p/ achar o n-esimo 
maior elemento:"; 
 cin>>n; 
 if (n <= |A| + |B|) { 
 ia = 1; 
 ib = 1; 
 for (i = 0; i < n; i++) 
 if (A[ia] > B[ib]) { 
 x = A[ia]; 
 ia++; 
 } 
 else { 
 x = B[ib]; 
 ib++; 
 } 
 } 
 
 cout<<i<<"-esimo maior elemento = "<<x; 
} 
Algoritmos e Estrutura de Dados II 
Ex. 2 
T(n) = 2T(n/2) + n; 
T(1) = 1; 
esq = 1; 
dir = n; 
achou = false; 
while (!achou && esq < dir){ 
 i = (esq + dir)/2; 
 if (A[i] >= x) 
 if (A[i+1] <= x) 
 achou = true; 
 else 
 esq = i+1; 
 else 
 dir = i; 
} 
if (achou) 
 cout<<"\nSera inserido na posicao "<<i+1; 
else { 
 i = (esq + dir)/2; 
 if (x > A[i]) 
 cout<<"\nSera inserido na posicao "<<i; 
 else 
 cout<<"\nSera inserido na posicao "<<i+1; 
} 
 
Algoritmos e Estrutura de Dados II 
Ex. 3 
T(n) = 2T(n/2) + n; 
T(1) = 1; 
int somatorio(int a) { 
 
int soma, i; 
 
 soma = 0; 
 for (i = 1; i <= a; i++) 
 soma := soma + i; 
 return soma; 
end; 
 
Algoritmos e Estrutura de Dados II 
Ex. 5 
T(n) = 2T(n/2) + n; 
T(1) = 1; 
typedef char TipoTexto[MaxTexto]; 
typedef char TipoPadrao[MaxPadrao]; 
void ForcaBruta (TipoTexto T, int n, TipoPadrao P, int m) 
//-- Pesquisa o padrao P[0..m-1] no texto T[0..n-1] – 
{ 
int i, j, k; 
for (i = 0; i < n; i++) { 
 k = i; j = 0; 
 while ((j < m) && (T[k] == P[j])) { 
 k++; 
 j++; 
 } 
 if (j == m) { 
 printf("Casamento na posicao %d\n", i); 
 break; // sai do for 
 } 
} 
}