Complexidade de Algoritmos (exemplos)

Procura Sequencial

Pior caso: analisa todos os N elementos: tempo é O(N)
Melhor caso: analisa apenas o 1º elemento: tempo é O(1)

 int search(int a[], int v, int l, int r) {
   int i;
   for (i = l; i <= r; i++)
     if (v == a[i]) return i;
   return -1;
 }

Procura Binária

Pior caso: Pior caso: analisa um número de elementos igual a [log N]+1: tempo é O(log N)

 int search(int a[], int v, int l, int r) { 
   while (r >= l) {
     int m = (l+r)/2;
     if (v == a[m]) return m;
     if (v < a[m]) r = m-1; else l = m+1;
   }
   return -1;
 }

Preenchimento de Matriz

Pior caso: são preenchidas N² entradas da matriz: tempo é O(N²)

 int mat_read(int mat[N][N]) {
   int i, j;
   for (i = 0; i < N; i++)
     for (j = 0; j < N; j++)
       scanf("%d", &mat[i][j]);
   return -1;
 }

Multiplicação de matrizes

Pior caso: três ciclos de N iterações encadeados: tempo é O(N³)

 int mat_mult(int matA[N][N], int matB[N][N], int matC[N][N]) {
   int i, j, k;
   for (i=0; i<N; i++)
     for (j=0; j<N; j++) {
       matC[i][j] = 0;
       for (k=0; k<N; k++)
         matC[i][j] += matA[i][k] * matB[k][j];
     }
 }

Pesquisa Binária (outro exemplo)

Este exemplo mostra como uma implementação cuidada pode melhorar o desempenho de um algoritmo.

O algoritmo procura um par de parcelas que produzam a soma fornecida. Os dados de entrada para o algoritmo, assim como a função main, são como se segue.

 static int vect[] = { -1, 1, 2, 4, 6, 8, 10, 15, 20, 25 };
 static int size   = 10;
 int main(int argc, char **argv) {
   int p1, p2, y = lookup(vect, size, atoi(argv[1]), &p1, &p2);
   if (y > 0) printf("%d %d\n", p1, p2);
 }

Primeira versão: utilização de uma função pré-definida

Tempo de execução: T(N) = O(N log N).

 int lookup(int v[], int sz, int x, int *p1, int *p2) {
   int i;
   for (i=0; i < sz; i++) {
     int d = x - v[i], y;
     y = search(v, d, 0, sz-1);  /* procura binária */
     if (y > 0) { *p1 = i; *p2 = y; return 1; }
   }
   return -1;
 }

Segunda versão: implementação dedicada

Tempo de execução: T(N) = O(N).

 int lookup(int v[], int sz, int x, int *p1, int *p2) {
   int i = 0, j = sz-1;
   while (i < j) {
     int sum = v[i] + v[j];
     if      (sum > x) j--;
     else if (sum < x) i++;
     else { *p1 = i; *p2 = j; return 1; }
   }
   return -1;
 }