Complexidade de algoritmos

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ções fundamentais 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 apenas uma 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 ou superior). 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<n; 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 encontra ordenada. 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á