Root at 16:48, 27 May 2005

2005-05-27T16:48:11Z

New page

== 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;
}

Complexidade de Algoritmos (exemplos) - Revision history

Root at 16:48, 27 May 2005