Complexidade de Algoritmos em C com exemplos e análise detalhada

Introdução 🔎

Quando se trata de programação, a complexidade do algoritmo é uma medida importante que ajuda a entender a eficiência do código. A complexidade é medida pela quantidade de tempo e espaço necessários para executar um algoritmo. Neste artigo, vamos explorar as diferentes complexidades de algoritmos com exemplos em C.

Complexidades de algoritmos 📊

Existem diferentes tipos de complexidades de algoritmos que são classificadas com base em seu tempo de execução. Aqui estão as complexidades mais comuns:

- O(1) (constante)

- O(log n) (logarítmica)

- O(n) (linear)

- O(n log n) (quase-linear)

- O(n²) (quadrática)

- O(n³) (cúbica)

- O(2ⁿ) (exponencial)

Cada uma dessas complexidades representa a quantidade de tempo necessário para executar um algoritmo em relação ao tamanho da entrada.

Exemplos de tempos de execução 🧪

Para entender melhor como as diferentes complexidades de algoritmos afetam o tempo de execução, vamos ver alguns exemplos.

Suponha que temos um vetor de números e queremos encontrar o menor valor. Se usarmos um algoritmo simples de busca linear, a complexidade será O(n) porque precisamos verificar cada elemento do vetor. Se o vetor tiver 1000 elementos, a busca levará 1000 operações.

Agora, se usarmos um algoritmo de busca binária, que é mais eficiente, a complexidade será O(log n). Se o vetor tiver 1000 elementos, a busca levará apenas 10 operações.

Outro exemplo é o algoritmo de ordenação bubble sort, que tem complexidade O(n²). Se tivermos um vetor de 1000 elementos, a ordenação levará 1.000.000 de operações.

Por outro lado, o algoritmo de ordenação quick sort tem complexidade O(n log n). Se tivermos um vetor de 1000 elementos, a ordenação levará cerca de 10.000 operações.

Mais exemplos de complexidades 🕵️‍♀️

Aqui estão mais alguns exemplos de algoritmos com diferentes complexidades:

- O(1) - Acesso a um elemento de um array.

int vetor[10] = {0};
int x = vetor[5]; // acesso ao elemento vetor[5] é O(1)

- O(log n) - Busca binária em uma árvore binária de busca.

struct no {
    int valor;
    struct no *esquerda, *direita;
};

struct no* busca_binaria(struct no* raiz, int valor) {
    if (raiz == NULL || raiz->valor == valor)
        return raiz;

    if (raiz->valor < valor)
        return busca_binaria(raiz->direita, valor);

    return busca_binaria(raiz->esquerda, valor);
}

- O(n) - Busca linear em uma lista simplesmente encadeada.

struct no {
    int valor;
    struct no *prox;
};

struct no* busca_linear(struct no* inicio, int valor) {
    struct no* atual = inicio;
    while (atual != NULL) {
        if (atual->valor == valor)
            return atual;
        atual = atual->prox;
    }
        return NULL;
}

- O(n log n) - Algoritmo de ordenação merge sort.

void merge(int arr[], int l, int m, int r) {
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;
 
    int L[n1], R[n2];
 
    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];
 
    i = 0;
    j = 0;
    k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        }
        else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
 
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
 
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}
 
void merge_sort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
 
        merge_sort(arr, l, m);
        merge_sort(arr, m + 1, r);
 
        merge(arr, l, m, r);
    }
}

- O(n²) - Algoritmo de ordenação bubble sort.

void bubble_sort(int arr[], int n) {
    int i, j;
    for (i = 0; i < n-1; i++)       
        for (j = 0; j < n-i-1; j++)
            if (arr[j] > arr[j+1])
                swap(&arr[j], &arr[j+1]);
}

- O(2ⁿ) - Algoritmo de busca em profundidade em um grafo.

void dfs(int u) {
    visitado[u] = true;
    for (int v : adj[u]) {
        if (!visitado[v])
            dfs(v);
    }
}

🧐 Conclusão:

A complexidade do algoritmo é uma consideração importante quando se trata de programação eficiente. Ao escolher um algoritmo para resolver um problema, é importante considerar a complexidade em relação ao tamanho da entrada. Algoritmos com complexidade de tempo exponencial, por exemplo, podem ser extremamente lentos para entradas maiores e, portanto, devem ser evitados sempre que possível.