Data de validade

Algoritmos, Análise
Prof. Ricardo Reis
Universidade Federal do Ceará
Sistemas de Informação
Estruturas de Dados
2 de maio de 2013

1

Introdução

2

Um algoritmo é um procedimento expresso em forma lógica não ambígua para resolução de um problema e cuja construção independe de linguagem de programação ou hardware utilizados. Implementar um algoritmo significa escrevê-lo numa linguagem de programação para posterior execução. O tempo de execução, numa dada máquina, da implementação de um algoritmo varia em função do número de instruções que os processadores presentes são capazes de efetuar por unidade de tempo e também das condições de processamento
(memória livre, total de processos em andamento, número de processadores envolvidos, condições de tráfico em rede e etc).
Para evitar análises dependentes de tempo considera-se que um algoritmo é subdividido, ao invés de em milissegundos, em uma quantidade finita de passos onde um passo pode ser interpretado como uma instrução indivisível e de tempo constante, ou seja, independente de condições de entrada ou processamento.
A quantidade de passos necessários ao cumprimento de um algoritmo é denominada de complexidade do algoritmo. A complexidade é em geral sensível a alguma característica da entrada do algoritmo e por essa razão é frequentemente expressa como uma função matemática f (n) onde n é a característica (por exemplo, o valor de uma entrada numérica, o comprimento de um vetor e etc).

Medindo a Complexidade de Algoritmos

As ilustrações dessa sessão apresentam alguns algoritmos clássicos e a determinação de suas respectivas complexidades.
I LUSTRAÇÃO -1 (Soma de Matrizes): Sejam
A e B duas matrizes quadradas de ordem n que devem ser somadas. O Algoritmo1 ilustra a resolução do problema. Haja vista que o tempo total da soma é sensível ao número de elementos envolvidos então é conveniente expressar a complexidade deste algoritmo em função de n. Além disso, sendo a soma