Analise de algoritmos: listas e árvores

Universidade Federal do Rio Grande do Norte CEA0008 – Estrutura de Dados Professor: João Paulo

Listas e Árvores

Monnalisa Christina Pereira de Medeiros

Caicó 2011

Aplicações da análise de complexidade de algoritmos

A Análise de Algoritmos, ou o cálculo da Complexidade de Algoritmos é uma tarefa indispensável para a construção de algoritmos bons e eficientes. Além da possibilidade de estimar o tempo de execução de um algoritmo, o cálculo da complexidade serve para auxiliar a escolha de um, dentre vários algoritmos que resolvam o mesmo problema. O motivo para se analisar um algoritmo é apurar melhor suas características e avaliar a viabilidade de sua utilização prática. Também é desejável saber quanto tempo um algoritmo particular irá consumir durante sua execução ou quanto espaço irá requerer para poder certificar-se da sua eficiência. Complexidade Computacional é a área da Ciência da Computação que explica as razões do por que alguns problemas são tão difíceis de serem resolvidos por computadores. A complexidade de um algoritmo está relacionada com o esforço computacional necessário para a sua execução. Ou seja, mesmo que se tenha uma maquina rápida, seu desempenho será limitado se estiver rodando um algoritmo ruim.

Aplicações de árvore binária

A estrutura de árvore binária tem muitas aplicações na computação. Um exemplo é a árvore de decisão utilizada em Inteligência Artificial. Nela existem situações em que se pretende chegar a uma conclusão dentro de um determinado domínio e através de respostas como "sim" ou "não", às questões que são formuladas permitem o avanço. Caso a resposta seja "não" avançasse para a direita e para o filho esquerdo caso a resposta seja "sim". Outro exemplo é em um sistema com um tráfego de dados grande (inclusões, alterações, exclusões), e que o tempo de acesso a esses dados seja vital para uma tomada de decisão. Árvores binárias oferecem grande poder, flexibilidade e eficiência quando usadas em programas de