BEM VINDO
À REVOLUÇÃO
Teoria da computabilidade e complexidade
Para melhor entendermos a complexidade de tempo e espaço precisamos definir alguma medida de eficiência. Em algoritmo tal medida é dada pelo seu tempo de execução ou o espaço (ou memória) usado. Deste modo podemos avaliar a viabilidade do mesmo. Em relação ao tempo, consideramos o tempo total (em minutos, segundos, etc.). Porém, calcular o tempo total não é interessante por depender da máquina.
Em Análise de Algoritmos conta-se o número de operações consideradas relevantes realizadas pelo algoritmo e demonstra esse número como uma função de n.
Essas operações podem ser comparações, operações aritméticas, movimento de dados, etc. O número de operações realizadas por um determinado algoritmo pode depender da particular instância da entrada. Em geral interessa-nos o pior caso, isto é, o maior número de operações usadas para qualquer entrada de tamanho n.
Exemplo: Busca sequencial de um dado elemento em um vetor armazenando n elementos de forma aleatória.
Para casos médios levamos em consideração a distribuição uniforme e que o dado buscado está dentro do vetor. Vejamos o pior caso, melhor caso e o caso médio.
Como exemplo, considere o número de operações de cada um dos dois algoritmos que resolvem o mesmo problema, como função de n.
Algoritmo 1: f1(n) = 2n² + 5n operações
Algoritmo 2: f2(n) = 500n + 4000 operações
Desta forma o valor de n definirá qual algoritmo requer mais ou menos operações.