Analise e complexidade de algoritmos

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 complexidade de 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ória utilizado 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 quantidade de 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 de algoritmos 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 e viabilidade 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ço necessá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. É pouco usado 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 sendo normalmente 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