COMPLEXIDADE DE ALGORITMOS

COMPLEXIDADE DE ALGORITMOS

A complexidade do algoritimo

Algoritimos são instruções claras para resolver um problema. A complexidade dos algoritmos pode ser espacial e temporal.

Temporal: quanto tempo será necessário para que o algoritmo termine e dê a resposta?

Espacial: quanto de espaço será necessário para que o algoritmo possa trabalhar e dar a resposta?

Algoritmos intratáveis: São os algoritmos não polinomiais, soluções para estes são dificilmente encontradas em tempo hábil, embora uma solução ótima possa ser entrada o tempo para resolvê-la pode ser inestimável.

Algoritmos tratáveis: Indica que o problema pode ser resolvido em tempo útil, mesmo o pior caso deste algoritmo ainda é solucionável computacionalmente.

Algoritmos polinomiais determinísticos: São algoritmos que apresentam comportamento previsível. Dada uma determinada entrada (instância do problema), o algoritmo apresenta sempre a mesma saída e o mesmo “ponto de parada”.
Exemplo: Algoritmo para resolver a formula de Bhaskara.

Algoritmos polinomiais não-determinísticos: Tem uma proposta de solução leva ou não a uma resposta “sim”.
Exemplo: Choice “chuta” uma solução levando a uma resposta “sim” (e ele tem capacidade para isto).

Classes de complexidade P

Consiste nos problemas que podem ser resolvidos em tempo Polinomial. Qualquer problema deste conjunto pode ser resolvido por um algoritmo com tempo de execução O(n^k).

A maioria dos algoritmos possuem complexidade temporal O(n²), exemplos: Quick Short, HeapSort e o Bubble Sort que são algoritmos de ordenação.

Outro exemplo: É o Algoritmo Dijkstra

Descrição Dijkstra: Calcula o caminho de custo mínimo entre vértices de um grafo. Escolhido um vértice como raiz da busca, este algoritmo calcula o custo mínimo deste vértice para todos os demais vértices do grafo. Ele é bastante simples e com um bom nível de