Complexidade de algoritmos

Disponível somente no TrabalhosFeitos
  • Páginas : 2 (419 palavras )
  • Download(s) : 0
  • Publicado : 20 de outubro de 2012
Ler documento completo
Amostra do texto
Busca Binária
Algoritmo
1 int buscaBinaria(int v , int *a, int n) {
2
int low = 0;
3
int high = ( n – 1 );
4
int middle;
5
while ( low <= high ) {
6
middle = low + ( high – low ) / 2;
7
if ( v ==a[middle] ) {
8
return middle;
9
} else if ( v < a[middle] ) {
10
high = middle – 1;
11
} else {
12
low = middle + 1;
13
}
14
}
15
return -1;
16 }
Operação fundamental
Neste algoritmo as operaçõesfundamentais são as duas comparações nas linhas 7 e 9.
Análise do melhor caso
O melhor caso ocorre quando o elemento que se deseja encontrar está exatamente na metade
da lista. Neste caso ocorreria apenasuma operação, então ela pode ser expressa pela notação
por (1).
Análise do pior caso
O pior caso ocorre quando o elemento que se desejado se encontra em uma das extremidades
da lista (inferior ousuperior). Neste caso a lista com n elementos seria dividida k vezes de
acordo com o esquema abaixo:
Índice do
Vetor

1
2
|---------|

3

4

...

n

|-----------------------|
.
.
. k vezes|------------------------------------------|
Onde poderíamos dizer que 2 k = n, ou colocando k em função de n: k= log 2(n).
Par cada divisão do vetor haveriam 2 comparações, então a complexidade seria dada por:
Cp =2.k = 2. log 2(n)
Considerando que constantes não afetam a ordem da complexidade poderíamos re-escrever a
equação acima usando a notação O como O(log n).

Bubble Sort
Algoritmo
1
void bubbleSort( int*a, int n ) {
2
int swapped;
3
int tmp;
4
do {
5
swapped = 0;
6
for ( i=1; i 7
if ( a[i-1] > a[i] ) {
8
tmp = a[i-1];
9
a[i-1]=a[i];
10
a[i]=tmp;
11
swapped = 1;
12
}
13
}
14
} while (swapped );
15}
Operação fundamental
Neste algoritmo a operação fundamental é a comparação que ocorre na linha 7.
Análise do melhor caso
O melhor caso ocorre quando a lista de elementos já se encontraordenada. Neste caso o
algoritmo realiza n comparações e então termina. Esta situação pode então ser expressa por
(n).
Análise do pior caso
No pior caso o loop será executado n vezes e cada vez irá...
tracking img