---
tags: Lab_ICC_II
---
<center>
<h3>
Universidade de São Paulo (USP)<br>
Instituto de Ciências Matemáticas e de Computação (ICMC)<br>
</h3>
<h3>
Bacharelado de Ciências de Computação<br>
Disciplina: Laboratório de Introdução à Ciência da Computação II<br>
Professor: Leonardo Pereira<br><br>
Aluno: Guilherme Machado Rios (11222839)
</h3>
<h1>
Análise formal e contagem de operações para algoritmos de buscas
</h1>
</center>

## Introdução

Será feita a contagem de operações/análise formal de três algoritmos envolvendo busca em um vetor de inteiros previamente ordenad. O primeiro é uma simples busca sequencial, o segundo e terceiro uma busca binária, iterativa e recursiva, respectivamente.

## Contagem de operações linha a linha

Tomando:
- ***a***: atribuições e operações aritméticas
- ***c***: comparações
- ***p***: acesso a memória
- ***r***: retorno de função
- ***f***: chamada de função

Função ***recursive_bin_search()***:

int recursive_bin_search(int *vector, int key, int low, int high) {
    if (low > high) return NOT_FOUND; // lg(n)*[c] + c + r 

    int mid = (low + high) / 2; // lg(n)*[3*a]

    if (vector[mid] < key) { // lg(n)*[p + c]
        return recursive_bin_search(vector, key, mid + 1, high); 
    }
    else if (vector[mid] > key) { // lg(n)*[p + c]
        return recursive_bin_search(vector, key, low, mid - 1); 
        // lg(n)*[r + f + a]
    }

    return mid + 1;
    }

// Analisando uma única execução dessa função considerando 1 execução para
// cada ação entre colchetes, temos, com R(1) sendo o caso base:
// R(n) = [c + 3*a + p + c + p + c + r + f + a] + R(n/2)
// R(n) = 2*[c + 3*a + p + c + p + c + r + f + a] + R(n/4)
// R(n) = 3*[c + 3*a + p + c + p + c + r + f + a] + R(n/8)

// Para k chamadas:
// R(n) = k*[3*c + 4*a + 2*p + r + f] + R(n/(2^k))

// O pior caso acontece quando não achamos o elemento procurado, assim, podemos
// encontrar k analisando o caso base:
// n/2^k = 1 <=> n = 2^k <=> k = lg(n)

// Sendo assim, temos que a equação para uma busca recursiva completa, no pior
// caso, é dada por:

// f(n) = lg(n)*(c + 3*a + p + c + p + c + r + f + a) + [R(1)]

// com R(1) = (c + 3*a + p + c + p + c + r + f + a) + c + r, no pior caso ...

// f(n) = lg(n)*(3*c + 4*a + 2*p + r + f) + (4*c + 4*a + 2*p + 2*r + f) 

// Sendo c = a = p = r = f = K, temos:
/****************************
 | f(n) = 11K*(lg(n)) + 13K |
 ****************************/
 
// recursive_bin_search() -> O(lg(n))

Função ***iterative_bin_search()***:

int iterative_bin_search(int *vector, int key, int low, int high) {
    int mid = (low + high) / 2; // 3*a
    if (vector[mid] == key) return mid + 1; // p + c
    
    while (low <= high) { // lg(n)*[c] + c
        mid = (low + high) / 2; // lg(n)*[3*a]

        if (vector[mid] < key) low = mid + 1; // lg(n)*[p + c]
        else if (vector[mid] > key) high = mid - 1; // lg(n)*[p + c + a]
        else return mid + 1;
    }

    return NOT_FOUND; // [r]
}

// Para saber quantas iterações serão feitas por esse laço basta nos
// basearmos no algoritmo recursivo, dado que ambas se baseam na ideia 
// de divisão e  conquista, logo temos lg(n) iterações...

// f(n) = lg(n)*(c + 3*a + p + c + p + c + a) + 3*a + p + c + c + r
// f(n) = lg(n)*(3*c + 4*a + 2*p) + 3*a + p + c + c + r

// Sendo c = a = p = r = K, temos:
/**************************
 | f(n) = 9K*(lg(n)) + 7K |
 **************************/
 
// iterative_bin_search() -> O(lg(n))

Função ***sequential_search()***:

int sequential_search(int *vector, int key, int vector_len) {
    for (int i = 0; i < vector_len; i++) { // a+c + n*[c + 2*a]
        if (vector[i] == key) return i + 1; // n*[c]
    }

    return NOT_FOUND; // [r]
}

// f(n) = a + c + n*(c + 2*a + c)
// f(n) = n*(3*c + 2*a) + a + c

// Sendo c = a = K, temos:
/**********************
 | f(n) = 5K*(n) + 2K |
 **********************/
 
// sequential_search() -> O(n)

## Comparação

Analisando as contagens de operações verificamos exatamente a análise feita no [relatório informal](https://hackmd.io/@JBzC_xdjRMidk80D-obQHQ/r19_QG2SD). Vemos as buscas binárias se mostrando melhores no pior caso, com um leve sobressair do algoritmo iterativo, dado que a contagem para esse mostrou uma constante menor.