Analise e complexidade de algoritmos

Disponível somente no TrabalhosFeitos
  • Páginas : 3 (521 palavras )
  • Download(s) : 0
  • Publicado : 11 de abril de 2013
Ler documento completo
Amostra do texto
1 – Defina Algoritmo;
Algoritmo é uma sequência de “passos” lógicos para a obtenção de uma solução para um determinado tipo de problema.

2 – Defina Complexidade de um algoritmo.
A complexidadede um algoritmo consiste na quantidade de “trabalho” necessária para a sua execução.

3 – Como analisar a complexidade de um algoritmo.
Para analisar a complexidade são necessários três cálculos:
•Tempo de execução do algoritmo determinado pelas instruções executadas: quanto “tempo” é necessário para computar o resultado para uma instância do problema de tamanho n;
• Espaço de memóriautilizado pelo algoritmo: quanto “espaço de memória/disco” é preciso para armazenar a(s) estrutura(s) utilizada(s) pelo algoritmo.
• O esforço realizado por um algoritmo é calculado a partir da quantidadede vezes que a operação fundamental é executada.

4 – O que é análise assintótica?
Análise assintótica é um método de descrever o comportamento de limites. Exemplos incluem o desempenho dealgoritmos quando aplicados a um volume muito grande de dados de entrada, ou o comportamento de sistemas físicos quando eles são muito grandes, com o intuito de calcular o tempo total de processamento eviabilidade para determinados casos.

5 – Cite e explique as três perspectivas para análise de complexidade.
A análise de complexidade de pior, melhor e casos médios fornece uma medida de esforçonecessário para a execução de um programa em diferentes situações.
Melhor Caso:
Definido pelo símbolo Ω (ômega), é o método que consiste em assumir que vai acontecer o melhor caso. É poucousado e tem aplicação em poucos casos.
Pior caso:
É representado pelo símbolo O (Ômicron), e consiste basicamente em assumir o pior dos casos que podem acontecer, sendo muito usado e sendonormalmente o mais fácil de determinar.
Caso Médio:
É definido pelo símbolo Θ (Theta), dos três é o método mais difícil de determinar pois necessita de análise estatística e como tal muitos testes...
tracking img