Redes

Análise de algoritmos
1 Medindo os algoritmos

Uma das preocupações que temos quando contruímos algoritmos é sobre sua eciência. Quão rápido nosso algoritmo executa? No melhor caso? No pior caso? E no caso médio? Independetemente de para que computador ele será implementado, seja para uma máquina lenta do século passado, seja para um moderno processador multicore, precisamos de formas de medir a qualidade dos algoritmos. Tendo em vista a grande quantidade de arquiteturas, processadores, compiladores e sistemas operacionais, é de fundamental importância uma métrica que independa de todos esses fatores acima. A métrica que adotamos é bem simples: contamos os passos do algoritmo. Consideramos um passo do algoritmo aquele que sempre executa em tempo constante, independente dos parâmetros do seu algoritmo, quando executado em um computador especíco, qualquer que seja esse. Vejamos, por exemplo, o trecho de código em C: int main() { int a,b,c; scanf("%d", &a); scanf("%d", &b); c = a + b; printf("%d", &c); }

Podemos analisar o algoritmo acima da seguinte forma. Em primeiro lugar, ignoramos os aspectos especícos da linguagem C, como cabeçalhos de função e declarações de variável. Resta-nos, então, apenas quatro linhas, duas de leitura, uma de atribuição e outra de saida. A leitura recebe uma entrada de 32 bits, portanto um valor xo, que qualquer computador realiza em tempo determinado, contamos como um passo. A atribuição também possui valor xo, mas a expressão de soma é executada antes. Soma de dois valores de 32 bits, tempo constante, seguido de atribuição de valor de 32 bits, 1

tempo constante. Total de dois passos. A escrita é similar a leitura, é apenas o caminhoi inverso, de forma análoga temos tempo constante. Portanto contamos cinco passos. Assim temos que o algoritmo executa em tempo constante em qualquer computador para o qual ele seja implementado. A boa notícia é que para tais operações de entrada e saída de tamanho xo, expressões aritméticas e