Análise de Algoritmos: Otimização Dinâmica - Reorganização para Melhor Eficiência
- #Estrutura de dados
- #Lógica de Programação
Ao considerar a análise de algoritmos e estruturas de dados, a eficiência não se limita apenas ao tempo de execução. A organização dos dados também desempenha um papel crucial no desempenho de muitos algoritmos. Um cenário comum é o acesso frequente a registros específicos em uma tabela de dados. Para abordar esse requisito, podemos empregar técnicas de reorganização contínua, visando posicionar os registros mais acessados no início da lista, otimizando assim as operações de busca sequencial.
Método de "Mover para Frente":
Um método prático é o chamado "mover para frente", onde cada vez que um registro é acessado com sucesso, ele é movido para o início da lista. Neste método, a prioridade máxima é dada ao registro mais recentemente acessado, tornando-se ideal para buscas sequenciais. Vejamos um exemplo:
// Antes da busca bem-sucedida
[0, 0, 0, 0, X, 0, 0, 0]
// Após a busca bem-sucedida
[X, 0, 0, 0, 0, 0, 0, 0]
Essa abordagem visa otimizar o acesso aos registros frequentemente buscados, melhorando o desempenho geral.
Método de "Transposição":
Outra técnica valiosa é a "transposição", na qual um registro encontrado com sucesso é trocado pelo registro imediatamente anterior. Nesse caso, o registro só é movido para o início se sua frequência de busca o justificar. Este método é particularmente eficaz para buscas não ordenadas. Vejamos um exemplo:
// Antes da busca bem-sucedida
[0, 0, 0, 0, X, 0, 0, 0]
// Após a busca bem-sucedida
[0, 0, 0, X, 0, 0, 0, 0]
A estratégia de transposição destaca-se em cenários onde a busca bem-sucedida indica uma alta probabilidade de busca subsequente, resultando em uma organização mais eficiente dos dados.
Em conclusão, a escolha entre "mover para frente" e "transposição" dependerá do padrão de acesso aos dados e das características específicas do problema em questão. Ambas as técnicas oferecem uma maneira dinâmica de otimizar a organização dos registros, contribuindo para a eficiência global do algoritmo.
Aqui vai um exemplo em Linguagem C bem comentado para vocês entenderem:
#include <stdio.h>
#include <locale.h>
// Função para mover o elemento encontrado para o início da lista
void mover_para_frente(int registros[], int indice){
int temp = registros[indice];
// Desloca os elementos para a direita, abrindo espaço para o elemento encontrado
for (int i = indice; i > 0; i--){
registros[i] = registros[i - 1];
}
// Coloca o elemento encontrado no início da lista
registros[0] = temp;
}
// Função para realizar a transposição do elemento encontrado com o anterior
void transposicao(int registros[], int indice) {
int temp = registros[indice];
registros[indice] = registros[indice - 1];
registros[indice - 1] = temp;
}
// Função de busca linear para encontrar o índice do elemento procurado no array
int buscaLinear(int arr[], int tamanho, int elemento){
for (int i = 0; i < tamanho; i++){
if (arr[i] == elemento){
return i; // Retorna o índice do elemento encontrado
}
}
return -1; // Retorna -1 se o elemento não for encontrado
}
int main(){
setlocale(LC_ALL, "Portuguese");
printf("Exemplo de ordenação Mover-Para-Frente\n");
// Array de exemplo
int tabela1[] = {3, 12, 55, 1, 10, 5, 6, 77};
int tamanho = sizeof(tabela1) / sizeof(tabela1[0]);
int elementoProcurado = 10;
// Busca o índice do elemento procurado usando busca linear
int indice1 = buscaLinear(tabela1, tamanho, elementoProcurado);
printf("Antes de Mover para Frente: \n");
for (int i = 0; i < 8; i++) {
printf("%d ", tabela1[i]);
}
printf("\n");
// Move o elemento encontrado para o início da lista
mover_para_frente(tabela1, indice1);
printf("Após Mover para Frente: \n");
for (int i = 0; i < 8; i++) {
printf("%d ", tabela1[i]);
}
printf("\n");
printf("Exemplo de ordenação Transposição\n");
// Array de exemplo
int tabela2[] = {3, 12, 55, 1, 10, 5, 6, 77};
// Busca o índice do elemento procurado usando busca linear
int indice2 = buscaLinear(tabela2, tamanho, elementoProcurado);
printf("Antes da Transposição: \n");
for (int i = 0; i < 8; i++) {
printf("%d ", tabela2[i]);
}
printf("\n");
// Realiza a transposição do elemento encontrado com o anterior
transposicao(tabela2, indice2);
printf("Após a Transposição: \n");
for (int i = 0; i < 8; i++) {
printf("%d ", tabela2[i]);
}
printf("\n");
}
