Redes

Disponível somente no TrabalhosFeitos
  • Páginas : 3 (520 palavras )
  • Download(s) : 0
  • Publicado : 8 de maio de 2012
Ler documento completo
Amostra do texto
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 demedir 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 todosesses 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âmetrosdo 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 devariá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 tempodeterminado, 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 de32 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 temosque 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...
tracking img