Os algoritmos são fundamentais para a ciência da computação e desenvolvimento de software. Eles são procedimentos ou fórmulas passo a passo para resolver problemas. Para avaliar e comparar algoritmos, frequentemente usamos a notação Big O. Este artigo apresentará os conceitos básicos de algoritmos e notação Big O, fornecendo o conhecimento fundamental necessário para analisar e otimizar código.
Um algoritmo é um conjunto finito de instruções que, quando seguidas, executam uma tarefa específica ou resolvem um problema particular. Os algoritmos podem variar de simples (como somar dois números) a complexos (como ordenar uma lista de milhões de números).
- Entrada: O algoritmo recebe zero ou mais entradas.
- Saída: Ele produz pelo menos uma saída.
- Definitude: Cada passo é claramente definido.
- Finitude: O algoritmo termina após um número finito de passos.
- Efetividade: Cada passo é básico o suficiente para ser executado, em princípio, por um humano usando lápis e papel.
A notação Big O é um conceito matemático usado para descrever a eficiência de um algoritmo em termos de tempo e espaço. Ela descreve especificamente o pior cenário, fornecendo um limite superior no tempo ou espaço necessários como uma função do tamanho da entrada.
- O(1): Tempo constante - O desempenho do algoritmo é independente do tamanho da entrada.
- O(log n): Tempo logarítmico - O desempenho aumenta logaritmicamente conforme o tamanho da entrada aumenta.
- O(n): Tempo linear - O desempenho aumenta linearmente com o tamanho da entrada.
- O(n log n): Tempo linearítmico - Uma combinação de crescimento linear e logarítmico.
- O(n^2): Tempo quadrático - O desempenho é proporcional ao quadrado do tamanho da entrada.
- O(2^n): Tempo exponencial - O desempenho dobra a cada adição ao conjunto de dados de entrada.
- O(n!): Tempo fatorial - O desempenho é uma função fatorial do tamanho da entrada.
- O(1): Acessar um elemento em um array por índice.
- O(log n): Busca binária em um array ordenado.
- O(n): Iterar por uma lista.
- O(n log n): Algoritmos de ordenação eficientes como Merge Sort e Quick Sort.
- O(n^2): Algoritmos de ordenação simples como Bubble Sort, Insertion Sort e Selection Sort.
- O(2^n): Resolver o problema das Torres de Hanói.
- O(n!): Resolver o problema do caixeiro viajante com uma abordagem de força bruta.
A complexidade de tempo é uma função que descreve a quantidade de tempo computacional que um algoritmo leva em relação ao tamanho da entrada. Ela ajuda a determinar a escalabilidade do algoritmo.
A complexidade de espaço refere-se à quantidade de memória que um algoritmo precisa para ser executado até a conclusão. É importante ao considerar limitações de memória e eficiência.
Vamos analisar a complexidade de tempo de um algoritmo simples que soma todos os elementos de um array:
fun sumArray(arr: IntArray): Int {
var total = 0
for (num in arr) {
total += num
}
return total
}- Tamanho da Entrada (n): O número de elementos no array.
- Número de Operações: O loop executa
nvezes, cada vez realizando uma operação de adição de tempo constante. - Complexidade de Tempo: O(n), porque o tempo necessário para completar a função cresce linearmente com o tamanho da entrada.
Explicação: O Bubble Sort é um algoritmo de comparação simples onde cada par de elementos adjacentes é comparado, e os elementos são trocados se estiverem na ordem errada. Este processo se repete desde o início da lista até que a lista esteja ordenada.
Vantagens:
- Fácil de entender e implementar.
- Não requer memória adicional (ordenação in-place).
Desvantagens:
- Muito ineficiente para grandes conjuntos de dados.
- Desempenho ruim comparado a outros algoritmos de ordenação.
Complexidade de Tempo:
- Melhor Caso: O(n) (quando o array já está ordenado).
- Caso Médio: O(n^2).
- Pior Caso: O(n^2).
Explicação: O Selection Sort divide a lista em uma região ordenada e uma região não ordenada. Ele repetidamente seleciona o menor (ou maior, dependendo da ordem de ordenação) elemento da região não ordenada e o move para o final da região ordenada.
Vantagens:
- Simples de implementar.
- Desempenha bem em listas pequenas.
Desvantagens:
- Ineficiente em listas grandes.
- O número de comparações é fixo (n(n-1)/2), levando a um desempenho ruim.
Complexidade de Tempo:
- Melhor Caso: O(n^2).
- Caso Médio: O(n^2).
- Pior Caso: O(n^2).
Explicação: O Quick Sort é um algoritmo de divisão e conquista. Ele seleciona um elemento 'pivô' e particiona o array em dois sub-arrays, de acordo com se os elementos são menores ou maiores que o pivô. Os sub-arrays são então ordenados recursivamente.
Vantagens:
- Eficiente para grandes conjuntos de dados.
- Geralmente tem um desempenho melhor que outros algoritmos O(n log n) na prática.
- Ordenação in-place (requer pouca memória adicional).
Desvantagens:
- O desempenho pode degradar para O(n^2) se a seleção do pivô for ruim.
- Implementação recursiva pode levar a estouro de pilha para listas muito grandes.
Complexidade de Tempo:
- Melhor Caso: O(n log n).
- Caso Médio: O(n log n).
- Pior Caso: O(n^2).
Explicação: O Insertion Sort constrói o array ordenado um elemento de cada vez. Ele pega cada elemento e o insere em sua posição correta dentro da parte já ordenada do array, deslocando elementos conforme necessário.
Vantagens:
- Simples de implementar.
- Eficiente para conjuntos de dados pequenos ou quase ordenados.
- Ordenação estável (mantém a ordem relativa dos elementos iguais).
Desvantagens:
- Ineficiente para grandes conjuntos de dados.
- Mais deslocamentos e comparações em comparação com algoritmos mais avançados.
Complexidade de Tempo:
- Melhor Caso: O(n) (quando o array já está ordenado).
- Caso Médio: O(n^2).
- Pior Caso: O(n^2).
O algoritmo de Dijkstra é um algoritmo fundamental na teoria dos grafos, usado para encontrar os caminhos mais curtos entre nós em um grafo, que podem representar, por exemplo, redes rodoviárias.
O algoritmo de Dijkstra funciona selecionando iterativamente o nó com a menor distância tentativa, atualizando as distâncias para seus vizinhos e marcando o nó como "visitado". Esse processo continua até que todos os nós tenham sido visitados ou o caminho mais curto para o nó alvo tenha sido encontrado.
-
Inicialização:
- Defina a distância para o nó inicial como zero.
- Defina a distância para todos os outros nós como infinita.
- Defina todos os nós como não visitados.
- Defina o nó inicial como o nó atual.
-
Visite o Nó Atual:
- Para o nó atual, considere todos os seus vizinhos não visitados e calcule suas distâncias tentativas (distância do nó atual + peso da aresta até o vizinho).
- Se a distância tentativa calculada for menor que a distância conhecida atualmente para o vizinho, atualize a distância mais curta para o vizinho.
-
Marcar como Visitado:
- Após visitar todos os vizinhos do nó atual, marque o nó atual como visitado. Um nó visitado não será verificado novamente.
-
Selecione o Próximo Nó:
- Selecione o nó não visitado com a menor distância tentativa e defina-o como o novo nó atual.
- Repita o processo até que todos os nós sejam visitados ou o caminho mais curto para o nó alvo seja determinado.
- Eficiência: Encontra eficientemente o caminho mais curto em grafos com pesos não negativos.
- Ampla Aplicabilidade: Útil em várias aplicações práticas, como sistemas de roteamento e navegação.
- Apenas Pesos Não Negativos: Não lida com grafos com arestas de peso negativo. Para tais grafos, o algoritmo de Bellman-Ford é mais apropriado.
- Caminho Mais Curto de Fonte Única: Encontra os caminhos mais curtos de um único nó fonte para todos os outros nós. Se forem necessárias várias fontes, o algoritmo precisa ser executado várias vezes.
- Complexidade de Espaço: Requer memória adicional para manter o conjunto de nós não visitados e a tabela de distâncias.
A complexidade de tempo do algoritmo de Dijkstra depende das estruturas de dados usadas:
- Usando uma lista simples: O(V^2), onde V é o número de vértices.
- Usando uma fila de prioridade (heap binário): O((V + E) log V), onde E é o número de arestas.
- Usando um heap de Fibonacci: O(E + V log V), que é mais eficiente para grafos com um grande número de arestas.
Imagine um grafo que representa uma rede rodoviária onde os nós são interseções e as arestas são estradas com pesos que representam a distância de viagem:
(A)
/ | \
1 3 6
/ | \
(B)-- 5 --(C)
\ | /
4 2 1
\ | /
(D)
-
Inicialização:
- Comece no nó A.
- Defina a distância para A = 0, e as distâncias para B, C, D = ∞.
-
Visite A:
- Atualize as distâncias para os vizinhos: B (1), C (3), D (6).
- Marque A como visitado.
-
Selecione B (menor distância tentativa):
- Atualize as distâncias para os vizinhos: D (5 através de B).
- Marque B como visitado.
-
Selecione C:
- Atualize as distâncias para os vizinhos: D (5 através de C).
- Marque C como visitado.
-
Selecione D:
- Todos os vizinhos visitados, o algoritmo termina.
Caminhos mais curtos finais de A:
- A para B: 1
- A para C: 3
- A para D: 5
Busca Binária é um algoritmo eficiente para encontrar um item em uma lista ordenada de itens. Ele funciona dividindo repetidamente pela metade a porção da lista que pode conter o item até que você tenha reduzido as possíveis localizações a apenas uma.
A Busca Binária opera com base no princípio de divisão e conquista. O algoritmo compara o valor alvo com o elemento do meio da lista. Se o valor alvo coincidir com o elemento do meio, a busca é bem-sucedida. Se o valor alvo for menor que o elemento do meio, o algoritmo repete a busca na metade esquerda da lista. Se o valor alvo for maior, o algoritmo repete a busca na metade direita da lista. Esse processo continua, dividindo a lista ao meio a cada vez, até que o valor alvo seja encontrado ou a sublista tenha tamanho zero.
- Inicialização: Comece com toda a lista e determine o elemento do meio.
- Comparação: Compare o valor alvo com o elemento do meio.
- Seleção de Sublista: Com base na comparação, decida se deve buscar na sublista à esquerda ou à direita.
- Repetir: Continue o processo na sublista selecionada até que o valor alvo seja encontrado ou a sublista esteja vazia.
- Eficiência: A Busca Binária é muito mais rápida do que a busca linear para grandes conjuntos de dados. Ao dividir o espaço de busca pela metade a cada passo, ela reduz rapidamente o tamanho do problema.
- Desempenho previsível: A complexidade de tempo da busca binária é logarítmica, o que significa que ela cresce muito lentamente em relação ao tamanho da entrada.
- Implementação Simples: Uma vez que a lista está ordenada, a busca binária é relativamente simples de implementar.
- Requer Dados Ordenados: A Busca Binária só pode ser aplicada a uma lista que já esteja ordenada. Isso significa que há um custo inicial para ordenar a lista, caso não esteja ordenada.
- Sobrecarga para Listas Pequenas: Para listas muito pequenas, a sobrecarga das comparações e divisões repetidas pode tornar a busca binária menos eficiente do que uma busca linear simples.
- Complexidade com Dados Dinâmicos: Em cenários onde os dados mudam frequentemente, manter uma lista ordenada pode adicionar complexidade e sobrecarga.
- Melhor Caso: O(1) - O valor alvo é encontrado no meio da lista na primeira comparação.
- Caso Médio: O(log n) - A lista é dividida repetidamente, levando a um crescimento logarítmico em relação ao número de elementos.
- Pior Caso: O(log n) - O valor alvo está na última posição possível verificada, ainda requerendo um número logarítmico de etapas.