View source for Complexidade de Algoritmos (exemplos)

== Procura Sequencial ==

'''Pior caso''': analisa todos os N elementos: tempo é O(N)<br>
'''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 <code>main</code>, 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;
  }