complexidade

Complexidade TAD Pesquisa Binaria

Dicionario* dicionarioCria(int max) {
1
Dicionario* d = (Dicionario*) malloc(sizeof (Dicionario));
2
if (d != NULL) {
3
d->vals = (int*) malloc(max * sizeof (int));
4
if (d->vals != NULL) {
5
d->n = 0;
6
d->max = max;
7
return d;
8
} else
9
printf("nao foi possivel realizar a alocacao do vetor\n");
10
} else
11
printf("nao foi possivel alocar o dicionario\n");
12
}

Analise
As linhas 1-12 são O(1).
Portanto a complexidade do algoritmo e
O(1)

int pbin(Dicionario* d, int c) {
1
int esq, dir, i;
2
esq = 0;
3
dir = d->n - 1;
4
while (esq vals[i] == c)
7
return i;
8
if (c < d->vals[i])
9
dir = i - 1;
10
else
11
esq = i + 1;
12
}
13
return -1;
14
}

Analise
As linhas 1-3 são O(1). No interior do laço, ou seja, linhas 5-12, o custo de uma execução é O(1). A linha 13 é O(1). Resta determinar quantas vezes o laço é executado. Vamos considerar duas situações.
Seja n o tamanho do dicionário.
1) n é potência de 2
A cada iteração do laço, n é dividido ao meio. Isso é feito até que o tamanho que sobra é 1 (na iteração seguinte a condição do while torna-se false).
Vamos denotar por k o número de divisões realizadas. Então, n/2 k = 1 n = 2 k log 2 n = log 2 2 k [aplicando logaritmo a ambos os lados] log 2 n = k ou k = log 2 n
Portanto, se n é potência de 2, o número de vezes que o laço executa é O(log n).
2) n não é potência de 2
Veja que n sempre está entre duas potências de 2:
2 k n;
8
while (esq vals[i] >= c && d->vals[i - 1] vals[i])
13
dir = i - 1;
14
else
15
esq = i + 1;
16
}
17
return -1;
18
}

Analise
As linhas 1-7 são O(1). No interior do laço, ou seja, linhas 8-16, o custo de uma execução é O(1). A linha 17 é O(1). Resta