Complexidade computacional – Wikipédia  a enciclopédia livre
10 pág.

Complexidade computacional – Wikipédia a enciclopédia livre


DisciplinaAlgoritmos14.817 materiais172.977 seguidores
Pré-visualização6 páginas
a relação a × b = c descreve. Decidir se uma dada tripla é
membro deste conjunto corresponde a resolver o problema da multiplicação de dois números.
Medição do tamanho de uma instância
[nb 1]
Uma representação artística de uma
máquina de Turing
Para medir a dificuldade de resolver um problema computacional, pode-se desejar ver quanto tempo o melhor algoritmo necessita para
resolver o problema. No entanto, o tempo de execução pode, em geral, depender da instância. Em particular, instâncias maiores exigirão
mais tempo para resolver. Assim, o tempo necessário para resolver um problema (ou o espaço necessário, ou qualquer outra medida de
complexidade) é calculado em função do tamanho da instância. Isso geralmente leva em consideração o tamanho da entrada em bits. A
Teoria da Complexidade está interessada em como os de algoritmos crescem com um aumento no tamanho da entrada. Por exemplo, no
problema de descobrir se um grafo é conectado, quanto tempo a mais leva para resolver um problema para um grafo com 2n vértices
comparado ao tempo levado para um grafo com n vértices?
Se o tamanho da entrada é n, o tempo gasto pode ser expresso como uma função de n. Já que o tempo gasto em diferentes entradas de
mesmo tamanho pode ser diferente, o pior caso em complexidade de tempo T(n) é definido como sendo o tempo máximo dentre todas as
entradas de tamanho n. Se T(n) é um polinômio em n, então o algoritmo é dito ser um algoritmo de tempo polinomial. A tese de Cobham diz
que um problema pode ser resolvido com uma quantidade factível de recursos se ele admite um algoritmo de tempo polinomial.
Modelos de máquinas e medidas de complexidade
Máquina de Turing
Uma máquina de Turing é um modelo matemático de uma máquina de computação em geral. É um
dispositivo teórico que manipula símbolos contidos em uma tira de fita. Máquinas de Turing não
pretendem ser uma tecnologia de computação na prática, mas sim uma experiência de pensamento
que representa uma máquina de computação. Acredita-se que se um problema pode ser resolvido
por um algoritmo, então existe uma máquina de Turing que resolve o problema. Na verdade, esta é
a afirmação da tese de Church-Turing. Além disso, sabe-se que tudo o que pode ser computado
em outros modelos de computação conhecido por nós hoje, como uma máquina RAM, Jogo da
Vida de Conway, autômato celular ou qualquer linguagem de programação pode ser computado
em uma máquina de Turing. Como as máquinas de Turing são fáceis de analisar matematicamente,
e acredita-se que sejam tão poderosas quanto qualquer outro modelo de computação, a máquina
de Turing é o modelo mais comumente usado em teoria da complexidade.
Muitos tipos de máquinas de Turing são usados para definir as classes de complexidade, tais como máquinas de Turing determinísticas,
máquinas de Turing probabilísticas, máquinas de Turing não-determinísticas, máquinas de Turing quânticas, máquinas de Turing simétricas e
máquinas de Turing alternadas. Todas elas são igualmente poderosas, em princípio, mas quando os recursos (tais como tempo e espaço) são
limitados, algumas destas podem ser mais poderosas do que outras.
Uma máquina de Turing determinística é a máquina de Turing do tipo mais básico, que utiliza um conjunto fixo de regras para determinar suas
ações futuras. Uma máquina de Turing probabilística é uma máquina de Turing determinística com um suprimento extra de bits aleatórios. A
capacidade de tomar decisões probabilísticas muitas vezes ajuda algoritmos a resolverem problemas de forma mais eficiente. Algoritmos que
usam bits aleatórios são chamados algoritmos probabilísticos. A máquina de Turing não-determinística é uma máquina de Turing
determinística com uma característica adicional de não-determinismo, que permite que uma máquina de Turing tenha várias possíveis ações
futuras a partir de um determinado estado. Uma maneira de entender o não-determinismo é visualizar os ramos da máquina de Turing como
os vários caminhos computacionais possíveis a cada passo, e se ela resolve o problema em qualquer um desses ramos, diz-se ter resolvido o
problema. Evidentemente, este modelo não pretende ser um modelo fisicamente realizável, é apenas uma máquina abstrata teoricamente
interessante que dá origem a classes de complexidade particularmente interessantes. Por exemplo, veja algoritmo não-determinístico.
Outros modelos de máquinas
Muitos modelos de máquinas diferentes do padrão de máquinas de Turing multi-fitas têm sido propostos na literatura, por exemplo, máquinas
de acesso aleatório. Talvez surpreendentemente, cada um desses modelos pode ser convertido para outro, sem fornecer qualquer poder
computacional extra. O consumo de tempo e memória desses modelos alternativos pode variar. O que todos estes modelos têm em
comum é que as máquinas funcionam de forma determinística.
No entanto, alguns problemas computacionais são mais fáceis de analisar em termos de recursos mais incomuns. Por exemplo, uma máquina
de Turing não-determinística é um modelo computacional em que é permitido ramificar-se para verificar muitas possibilidades diferentes de
uma só vez. A máquina de Turing não-determinística tem muito pouco a ver com a forma como nós queremos fisicamente computar
algoritmos, mas a sua ramificação capta exatamente muitos dos modelos matemáticos que queremos analisar, de modo que o tempo não-
determinístico é um recurso muito importante na análise de problemas computacionais.
Medidas de complexidade
Para uma definição precisa do que significa resolver um problema utilizando uma determinada quantidade de tempo e espaço, um modelo
computacional tal como a máquina de Turing determinística é utilizado. O tempo exigido por uma máquina de Turing determinística M na
entrada x é o número total de transições de estado, ou etapas, que a máquina faz antes de parar e responder com a saída ("sim" ou "não").
Diz-se que a máquina de Turing M opera dentro do tempo f(n), se o tempo exigido por M em cada entrada de comprimento n é no máximo
f(n). Um problema de decisão A pode ser resolvido em tempo f(n) se existe uma operação da máquina de Turing em tempo f(n) que resolve
[1]
Visualização do algoritmo quicksort que
tem no caso médio desempenho 
.
o problema. Como a teoria da complexidade está interessada em classificar problemas com base na sua dificuldade, definem-se conjuntos de
problemas com base em alguns critérios. Por exemplo, o conjunto de problemas solucionáveis no tempo f(n) em uma máquina de Turing
determinística é então indicado por DTIME(f(n)).
Definições análogas podem ser feitas para os requisitos de espaço. Embora o tempo e o espaço sejam os mais conhecidos recursos de
complexidade, qualquer medida de complexidade pode ser vista como um recurso computacional. Medidas de complexidade são geralmente
definidas pelos axiomas de complexidade de Blum. Outras medidas de complexidade utilizadas na teoria da complexidade incluem a
complexidade de comunicação, a complexidade do circuito e a complexidade da árvore de decisão.
Melhor, pior e caso médio de complexidade
O melhor, o pior e o caso médio de complexidade referem-se a três maneiras diferentes de
medir a complexidade de tempo (ou qualquer outra medida de complexidade) de entradas
diferentes do mesmo tamanho. Uma vez que algumas entradas de tamanho n podem ser mais
rápidas para resolver do que outras, definimos as seguintes complexidades:
Complexidade no melhor caso: Esta é a complexidade de resolver o problema para a
melhor entrada de tamanho n.
Complexidade no pior caso: Esta é a complexidade de resolver o problema para a pior
entrada de tamanho n.
Complexidade no caso médio: Esta é a complexidade de resolver o problema na
média. Essa complexidade só é definida com relação a uma distribuição de
probabilidade sobre as entradas. Por exemplo, se todas as entradas do mesmo
tamanho são consideradas terem a mesma probabilidade de aparecer, a complexidade
do caso médio pode ser definida com relação à distribuição uniforme sobre todas as
entradas de tamanho n.
Por exemplo, considere