Wiki Computação

Ferramentas do usuário

Ferramentas do site

Visitou: • complexidade_computacional
c:complexidade_computacional

Tabela de conteúdos

Complexidade Computacional

Complexidade computacional ou teoria da complexidade computacional é o estudo do tempo e outros recursos necessarios para a execuçao de algoritmos em computadores. Niveis diferentes de complexidade computacional são divididos em classes, como: tempo polinomial (P), tempo polinomial não deterministico (NP), tempo exponencial (EXP) e tempo finito (R), sendo P ⊆ NP ⊆ EXP ⊆ R.

Classes de complexidade

As diferentes classes de complexidade dividem os problemas em relaçao a sua dificuldade computacional, usando como medida a sua “ordem de complexidade”, ou seja, a quantidade de tempo ou espaço necessaria para que dado problema seja computado, representada geralmente pela notaçao “Big-O”.

Notação "Big-O"

Antes de listar as classes de complexidade, é util entender a notaçao “Big-O”, ou “O()”. Considerando o valor de uma variavel “n”, a notaçao “O()” define a maneira que algoritmos se comportam a medida que “n” aumenta, em relaçao a quantidade de operaçoes.

Vejamos o seguinte exemplo: Certo algoritmo de multiplicaçao possui complexidade igual a O(n^2), logo: O(n^2) = 1 para n = 1, 4 para n = 2, e assim por diante. O que isso quer dizer neste exemplo, é que um computador teria de executar uma quantidade de operaçoes igual ao quadrado de “n” para realizar a multiplicaçao, sendo “n” a quantidade de algarismos de ambos os numeros sendo multiplicados. Pode-se notar que, e possivel que o numero de algarismos varie em cada um dos numeros na operação, como em 10·2, por exemplo. Mas, para calcular a complexidade de um dado algoritmo, é preciso considerar o seu comportamento no pior caso possivel, que aqui sempre será quando ambos os numeros tiverem a mesma quantidade de algarismos.

Tempo Polinomial

A classe de Tempo Polinomial ou “P”, abrange a ordem dos problemas que podem ser representados de acordo com uma funçao polinomial. Em outras palavras, todos os os problemas dessa classe podem ser representados com a notaçao O(n^k), onde k ∈ ℕ. Devido a isso, os tempo para a execuçao aumenta de forma relativamente pouco elevada. Alguns exemplos de problemas e algoritmos pertencentes a classe P:

  • Algoritmos de adiçao e subtraçao
  • Algoritmos de multiplicaçao (Por exemplo, o algoritmo Toom-3: O(N^1.465))
  • Algoritmo Euclidiano (O(N^2))
  • Metodo de Horner (θ(n))

Tempo Polinomial Não Determinístico

A classe de Tempo Polinomial Nao deterministico, NP, inclui problemas cuja soluçao pode ser verificada em Tempo Polinomial, uma vez que a possuimos, mas a obtençao da soluçao em si so pode ser obtida com algoritmos de tempo Exponencial. Essa classe compoe o principal problema aberto da ciencia da computaçao: P versus NP. O debate se resume a provar se problemas “completos em NP” (que possuem as caracteristicas de NP, e que podem ser reduzidos a qualquer outro problema NP) podem ser solucionados em Tempo Polinomial (note que, como todos os problemas completos em NP pode ser reduzidos uns aos outros, provar ou refutar essa questao para um dos problemas implicaria em fazer o mesmo para todos os demais.) Problemas da ordem NP sao considerados extremamente complexos, alguns de seus exemplos sao:

  • Problema matematico das 3 partiçoes
  • Partidas de Sudoku
  • Dobra de proteinas

Podemos ver que a classe NP contem um numero vasto e variado de problemas, abrangendo jogos de tabuleiro a problemas complexos nas areas de matematica e biologia.

Tempo Exponencial

A classe de Tempo Exponencial ou EXP é considerada a ultima e maior classe que contem problemas possiveis de serem solucionados computacionalmente. sua notaçao em ordem de complexidade é O(k^(n^c)), o que indica que muitos problemas desta ordem sao de extrema complexidade. Vale notar que, como P ⊆ NP ⊆ EXP, todos os problemas de P e NP podem ser resolvidos em tempo exponencial. Fora os exemplos mencionados nos topicos anteriores, alguns exemplos de problemas EXP e a avaliaçao de movimentos ideias em jogos como dama e xadrez.

Tempo Finito

Problemas de tempo finito (R) nao sao solucionaveis usando computaçao. O exemplo mais conhecido de um desses problemas e o “halting problem”. O problema consistia em demonstrar a possibilidade de determinar se um programa ira parar ou continuar para sempre. Em 1936, Alan Turing provou que um algoritmo como esse era impossivel de ser feito.

Referências

c/complexidade_computacional.txt · Última modificação: 2023/01/22 19:59 por Gabriel Bizio