Algoritmos são conjuntos de instruções que direcionam um computador para realizar uma tarefa específica. Eles estão presentes em todas as áreas da programação e são essenciais para otimizar o desempenho do código. O objetivo desse artigo é introduzir a importância dos algoritmos usando como exemplo a performance na ordenações de listas.
Imagine o seguinte cenário: temos uma lista de 10 números [3, 7, 2, 8, 1, 6, 9, 4, 5, 0] e queremos que seja ordenada do menor para o maior.
Nesse caso, dois algoritmos bastante conhecidos (não são os únicos e nem os melhores, mas servem como exemplo) na área de ordenação de listas são o bubble sort e o quick sort.
O bubble sort funciona da seguinte maneira: ele percorre a lista diversas vezes, comparando cada elemento com o seu sucessor e trocando o lugar de ambos caso necessário. Esse processo é repetido até que a lista esteja completamente ordenada. O tempo de execução médio desse algoritmo é O(n^2).
Nota: O() é uma notação de medida de complexidade de tempo chamada Big O. Em resumo, serve pra descrever quantas ações aquele algoritmo precisa performar pra que atinja seu objetivo
Imaginando nosso caso hipotético de uma lista com 10 números, cada número precisaria percorrer toda a lista e comparar os valores, o que são 10 ações pra cada elemento, por isso a complexidade de tempo é n^2, que no caso seria 10^2 = 10*10, que é igual a 100. Ou seja, o bubble sort requere 100 ações pra ordenar uma lista de 10 números. Extrapolando o exemplo pra uma lista de 100 números, a quantidade de ações requeridas sobe pra 10.000 (ou 100^2 = 100*100)!
Por outro lado, o quick sort é um algoritmo que utiliza uma estratégia conhecida como "dividir para conquistar". Ele escolhe um elemento da lista como pivô e, em seguida, divide a lista em duas partes: uma contendo elementos menores que o pivô e outra contendo elementos maiores que o pivô. Esse processo é repetido até que toda a lista esteja ordenada.
Voltando ao nosso caso de uma lista com 10 números, o quick sort escolheria um elemento do array para ser o pivô. Neste caso, vamos escolher o elemento do meio, que é o número 1.
O array é dividido em duas partes: uma parte com valores menores que o pivô e outra com valores maiores ou iguais ao pivô.
A parte dos menores valores fica à esquerda do pivô, e a parte dos maiores valores fica à direita do pivô. Os valores iguais ao pivô podem ficar em qualquer uma das partes.
A lista então é dividida em [3, 2, 1, 4, 0] e [7, 8, 6, 9, 5].
Agora devemos repetir o processo pra ambas as listas.
Vamos escolher um novo pivô para cada parte, e dividir o array novamente em duas partes: uma com valores menores que o pivô e outra com valores maiores ou iguais ao pivô.
Para a lista da esquerda, escolhemos o elemento 2 como pivô e dividimos em [1, 0] e [3, 2, 4]. Para a lista da direita, escolhemos o elemento 8 como pivô e dividimos em [7, 6, 5] e [9].
Agora repetimos o processo até que todas as partes do array tenham tamanho 1 ou 0. Quando uma parte do array tem tamanho 1 ou 0, significa que ela já está ordenada.
Ao final, o resultado será nossa lista ordenada da seguinte forma: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9].
O tempo de execução médio do quick sort, portanto, é O(n * log2(n)), que significa, nesse caso, 10 * log2(10) = 10 * 3,321 = 33,2. Extrapolando o exemplo pra uma lista de 100 números temos 100 * log2(100) = 100 * 6,643 = 664,3. Ou seja, o algoritmo de quick sort precisa performar, em média, 664,3 ações pra ordenar uma lista de 100 números, bem menor do que o tempo de execução do bubble sort, que precisa de 10.000 ações!
Apenas com o uso de algoritmos e matemática diminuímos em quase 1.400% o tempo de execução do nosso código, por isso o domínio do assunto é tão crucial para programadores.
Em resumo, os algoritmos são ferramentas importantes para a otimização do desempenho do código. Conhecer os fundamentos da programação é essencial para auxiliar na resolução de problemas de forma correta e eficiente.
Dica de leitura: Entendendo Algoritmos: Um Guia Ilustrado Para Programadores e Outros Curiosos, Aditya Y. Bhargava.
Top comments (2)
muito bom
ficou muito bom !!parabens ae