Complexidade algoritmo

Complexidade de Algoritmos
Siang Wun Song - Universidade de São Paulo - IME/USP

MAC 5710 - Estruturas de Dados - 2008

Siang Wun Song - Universidade de São Paulo - IME/USP

Complexidade de Algoritmos

Objetivo de estudar complexidade de algoritmos

Por que analisar a complexidade dos algoritmos? A preocupação com a complexidade de algoritmos é fundamental para projetar algoritmos eficientes. Podemos desenvolver um algoritmo e depois analisar a sua complexidade para verificar a sua eficiência. Mas o melhor ainda é ter a preocupação de projetar algoritmos eficientes desde a sua concepção.

Siang Wun Song - Universidade de São Paulo - IME/USP

Complexidade de Algoritmos

Eficiência ou complexidade de algoritmos

Para um dado problema considere dois algoritmos que o resolvem. Seja n um parâmetro que caracteriza o tamanho da entrada do algoritmo. Por exemplo, ordenar n números ou multiplcar duas matrizes quadradas n × n (cada uma com n2 elementos). Como podemos comparar os dois algoritmos para escolher o melhor?

Siang Wun Song - Universidade de São Paulo - IME/USP

Complexidade de Algoritmos

Complexidade de tempo ou de espaço

Precisamos definir alguma medida que expresse a eficiência. Costuma-se medir um algoritmo em termos de tempo de execução ou o espaço (ou memória) usado.
Para o tempo, podemos considerar o tempo absoluto (em minutos, segundos, etc.). Medir o tempo absoluto 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 expressa-se esse número como uma função de n. Essas operações podem ser comparações, operações aritméticas, movimento de dados, etc.

Siang Wun Song - Universidade de São Paulo - IME/USP

Complexidade de Algoritmos

Pior caso, melhor caso, caso médio
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, i.e., o maior