Complexidade de Algoritmo

COMPLEXIDADE TEMPORAL

A complexidade temporal de um algoritmo pode ser expressa em termos de números de operações usadas por um algoritmo quando a entrada tem um determinado tamanho. Essas operações podem ser de comparação, adição, multiplicação e divisão de números inteiros.

A complexidade temporal é descrita em termos do número de operações necessárias em vez do tempo atual do computador, por causa da diferença de tempo necessária para computadores diferentes realizarem operações básicas. Além disso, é um pouco difícil quebrar todas as operações binárias que um computador usa, sendo que os computadores mais rápidos podem executar as operações binárias básicas (adição, multiplicação, comparação ou troca de dois bits) em um 1nanosegundo, mas os computadores domésticos podem precisar de 1 microsegundo, um tempo 1000 vezes mais longo para fazer as mesmas operações. Analisaremos agora a complexidade temporal de um algoritmo de busca.

Exemplo 6:

Descreva a complexidade temporal do algoritmo de busca linear.

Solução:

O número de comparações usadas pelo algoritmo será tomado como medida de complexidade temporal. A cada passo do laço no algoritmo, duas comparações são realizadas – uma para ver se o final da lista foi alcançado e outra para comparar o elemento x com um termo da lista. Por fim, uma comparação a mais é feita por fora do laço. Consequentemente, se x = ai,       2i + 1 comparações são usadas. As maiores comparações 2n + 2, são necessárias quando o elemento não está na lista. Neste caso, 2n comparações são usadas para determinar que x não é ai, para i = 1, 2, ..., n. uma comparação adicional é usada para finalizar o laço e uma comparação é feita por fora do laço. Então quando x não estiver na lista, um total de 2n + 2 comparações são usadas. Assim, definimos que uma comparação linear requer no máximo O(n) comparações.

COMPLEXIDADE DE PIOR CASO

O tipo de complexidade do exemplo acima é uma análise do pior caso. Por esta análise, entendemos o maior número de operações necessárias para resolver o problema dado usando este algoritmo com uma entrada de determinado tamanho. A análise do pior caso nos diz quantas operações um algoritmo necessita para garantir que irá produzir uma solução.

Exemplo 7:

Qual é a complexidade de pior caso do insertionsort em termos de números de comparações feitas?

Solução:

        O insertionsort insere o j-ésimo elemento na ordem correta entre os primeiros j–1 elementos que já foram colocados na posição certa. Ele faz isso usando uma técnica de busca linear, comparando sucessivamente o j-ésimo elemento com o termo subsequente até um termo maior que, ou igual àquele seja encontrado, ou compara aj com ele mesmo e pára se aj não for menos que ele mesmo. Consequentemente, no pior caso, j comparações são necessárias para inserir o j-ésimo elemento na posição correta. Assim, o número total de comparações usadas pelo insertionsort para organizar uma lista de n elementos é:

Figura 1: número total de comparações usadas pelo insertionsort para organizar uma lista de n elementos

            Note que o insertionsort pode usar consideravelmente poucas comparações se os elementos menores aparecerem no final da lista. Com isso concluímos que o insertionsort tem complexidade pior caso O(n²) ??

ENTENDENDO A COMPLEXIDADE DE ALGORITMOS

            A tabela 1 apresenta a terminologia comumente usada para descrever a complexidade temporal dos algoritmos. Por exemplo, um algoritmo que encontra o maior termo dos primeiros 100 termos de uma lista de n elementos na sequencia dos 100 primeiros termos, em que n é um número inteiro com n maior igual a 100, tem complexidade constante. O algoritmo de busca linear tem complexidade linear (pior caso médio), e o algoritmo de busca binária tem complexidade logarítmica (pior caso). Há ainda algoritmos de complexidade polinomial, exponencial e fatorial.

Tabela 1: Terminologia usada para a Complexidade de Algoritmos

A tabela 2 apresenta o tempo necessário para resolver problemas de vários tamanhos com um algoritmo usando o número indicado de operações binárias, tempos com mais de 10elevado 100 anos são indicados com um asterisco. Na construção dessa tabela, considera-se que cada operação binária leva 10-9 segundos, sendo este o tempo necessário para uma operação binária que utilize os computadores mais rápidos da atualidade. No futuro, esses tempos tendem a diminuir à medida que os computadores mais rápidos forem sendo desenvolvidos.

Tabela 2: Tempo de Computação usado pelos algoritmos

É importante saber quanto tempo um computador precisa para resolver um problema. Por exemplo, se um algoritmo necessita de 10 horas, pode ser melhor gastar o tempo do computador para resolver este problema. Mas, se um algoritmo necessita de 10 bilhões de anos para resolver um problema seria irracional usar recursos para implementá-lo, sendo que um dos fenômenos mais interessantes da tecnologia moderna é o grande aumento da velocidade e da memória dos computadores.