Complexidade de Tempo em Teoria da Computação

Prévia do material em texto

PUC GOIÁS
ESCOLA DE CIÊNCIAS EXATAS E DA
COMPUTAÇÃO
CMP1067 Projeto e Análise de Algoritmos II
Marco A. F. Menezes
AULA 13
Referências: esta aula está baseada no seguinte livro,
1. Michael Sipser. Introdução à Teoria da Computação. Tradução: Ruy
José Guerra Barretto de Queiroz. São Paulo: Thomson Learning, 2007.
Aulas anteriores
Unidade 4 - Classes de Problemas
Ideia
4.1 Complexidade de tempo
Definição 4.1 Seja M uma máquina de Turing que pára sobre todas as
entradas. O tempo de execução ou complexidade de tempo de M é a função
f : N → N , em que f(n) é o número máximo de passos que M usa sobre
entradas de comprimento n. Se f(n) for o tempo de execução de M , dizemos
que M roda em tempo f(n) e que M é uma máquina de Turing de tempo
f(n).
Observação Considere f(n) = 6n3 + 2n2 + 20n + 45. Aqui, f(n) tem
quatro termos e o termo de mais alta ordem é 6n3. Desconsiderando o coefi-
ciente 6, dizemos que f é assintoticamente n3. Usamos a notação assintótica
1
f(n) é O(n3). Ainda, na análise do pior caso, a forma que consideramos
aqui, levamos em conta o tempo de execução mais longo dentre os gastos
para todas as entradas de um comprimento espećıfico. Na análise do caso
médio, consideramos a média dos tempos de execução para todas as entradas
de um comprimento espećıfico. Na análise do melhor caso, levamos em conta
o tempo de execução mais curto dentre os gastos para todas as entradas de
um comprimento espećıfico.
Exemplo Considere o problema de encontrar um elemento em uma lista
de tamanho n. Quais as complexidades (de tempo) no pior caso, no caso
médio e no melhor caso da máquina de Turing M que decide este problema?
M = ”Sobre a cadeia de entrada w:
1. Faça uma varredura da esquerda para a direita na fita.
2. Se no estágio 1 a fita continha o elemento, aceite. Senão, rejeite”.
Resolução
Definição 4.2 Seja t : N → R+ uma função. Dizemos classe de com-
plexidade de tempo, denotada por TIME(t(n)), como a coleção de todas as
linguagens que são decid́ıveis por uma máquina de Turing de tempo O(t(n)).
Exemplo Seja a linguagem decid́ıvel A = {0k1k; k ≥ 0}. Quanto tempo
uma máquina de Turing M precisa para decidir A?
M = ”Sobre a cadeia de entrada w:
1. Faça uma varredura na fita e rejeite se for encontrado algum 0 à direita
de algum 1.
2. Repita se existem ambos, zeros e uns, na fita:
3. Faça uma varredura na fita, cortando um único 0 e um único 1.
4. Se ainda permanecerem zeros após todos os uns tiverem sido cortados
ou se ainda permanecerem uns após todos os zeros tiverem sido corta-
dos, rejeite. Caso contrário, se não houver zeros nem uns sobre a fita,
aceite”.
2
Resolução
Observação Na teoria da complexidade, classificamos problemas com-
putacionais confome sua complexidade de tempo. Mas com qual modelo
medimos tempo? A mesma linguagem pode ter requisitos de tempo dife-
rentes em modelos diferentes.
Definição 4.3 Seja M uma máquina de Turing não determińıstica de-
cisora. O tempo de execução de uma máquina de Turing não determińıstica
M é a função f : N → N , em que f(n) é o número máximo de passos que M
usa sobre qualquer ramo de sua computação sobre entradas de comprimento
n.
Teorema 4.1 Seja t uma função tal que t(n) ≥ n. Então para toda
máquina de Turing não determińıstica de tempo t(n) existe uma máquina de
Turing equivalente de tempo 2O(t(n)).
Exerćıcios para casa Fazer a Lista 4.
Próxima aula Unidade 4 - Classes de problemas: a classe P .
3