MÓDULO 5 - COMPORTAMENTO ASSINTÓPTICO DE FUNÇÕES

Prévia do material em texto

1 
 
Módulo 5 -Tempo de Execução de um Programa: Comportamento 
Assintóptico de Funções 
 
O objeto de estudo módulo anterior foi aquele denominado decidibilidade, que é o 
estudo das propriedades exibidas pelas linguagens com o objetivo de determinar a 
existência ou não de um algoritmo capaz de aceitar ou rejeitar, em tempo e espaço 
finitos, uma cadeia qualquer apresentada para análise. Por outro lado, não basta um 
problema ser decidível. Há que se considerar os custos dessa solução. 
Custos dizem respeito ao tempo total de execução e ao volume total de memória 
para se chegar à solução do problema. 
 Complexidade Computacional 
Complexidade: “estudo das propriedades exibidas pelas linguagens com o objetivo 
de determinar o custo de seu processamento, em termos do tempo e espaço finitos” 
(RAMOS, VEGA e NETO, 2009). 
“A complexidade de tempo de uma computação mede a quantidade de trabalho 
gasto pela computação” (ROSA, J. L. G.). 
Seja n um parâmetro que caracteriza o tamanho da entrada do algoritmo. Por 
exemplo, ordenar n números ou multiplicar duas matrizes quadradas n x n (cada uma 
com n
2
 elementos). 
Costuma-se medir um algoritmo em termos de tempo de execução ou o espaço (ou 
memória) usado. Para o tempo, pode-se considerar o tempo absoluto (em minutos, 
segundos, etc.). Medir o tempo absoluto não é interessante, visto que depende da 
máquina. 
Em Análise de Algoritmos conta-se o número de operações consideradas relevantes 
realizadas pelo algoritmo e expressa-se esse número como uma função de n. Essas 
operações podem ser comparações, operações aritméticas, movimento de dados, etc. 
Tabela 1: Estudo comparativo da grandeza de algumas funções 
n log2(n) n*log2(n) n
2
 n
3
 2
n
 
1 0 0 1 1 2 
10 3.32 33 100 1000 1024 
100 6.64 664 10
4
 10
6
 1, 268 x10
30
 
1000 9.97 9970 10
6
 10
9
 1, 072 x 10
301
 
 
2 
 
Um caso de particular interesse é quando n tem valor muito grande (n  ), 
denominado comportamento assintótico. 
Complexidade de tempo 
Seja MT uma Máquina de Turing determinística. 
“A complexidade de tempo (tempo de execução) é a função f:  tal que f(n) é o 
número máximo de transições processadas por uma computação de MT quando iniciada 
com uma cadeia de entrada de comprimento n, independentemente de MT aceitar ou 
não.” (ROSA, J. L. G.) 
Assume-se que a computação termina para toda a cadeia de entrada. 
 
A notação  – grande  
Para se estudar o comportamento assintótico – para n grande – emprega-se o termo de 
ordem superior. 
Sejam f, g R
+, 
diz-se que f(n) = O(g(n)), se existirem números inteiros e positivos c 
e n0 tais que: 
 n, n  n0, f(n) < c. g(n) 
 A notação  é utilizada para dar um limite assintótico superior sobre uma 
função, dentro de um fator constante 
Operações com a notação  
Tabela 2 Operações com a notação  
f(n) = O(f(n)) 
c . f(n), c constante = O(f(n)) 
O(f(n)) + O(f(n)) = O(f(n)) 
O(O(f(n)) = O(f(n)) 
O(f(n)) + O(g(n)) = O(max(f(n), g(n))) 
O(f(n)) . O(g(n)) = O(f(n) . g(n)) 
f(n) . O(g(n)) = O(f(n) . g(n)) 
 Seja f(n) = n e g(n) = n2. Tem-se que n = O(n2). De fato, n2  n e, portanto, f(n) é 
O(n
2
), com constantes c = 1 e n0  0 
 
3 
 
 Seja f(n) = (n + 2)2, f(n) é (n2), com c = 5: De fato:n2 + 4n + 4  5 n2, para n  
2. 
 
Máquina de Turing de k fitas 
Teorema: seja L uma linguagem aceita por uma Máquina de Turing determinística de k 
fitas M com complexidade de tempo f(n). Então L é aceita por uma Máquina de Turing 
padrão de uma fita com complexidade de tempo  (f(n)
2
). 
Observe-se que a eliminação de fitas adicionais (de k fitas para 1 fita) transforma o 
tempo de execução para no máximo uma potência de 2. 
Não determinismo 
Definição: seja uma Máquina de Turing não determinística. A complexidade de tempo 
de M é a função f :  tal que f(n) é o número máximo de transições processadas 
por uma computação de M, empregando qualquer escolha de transições quando iniciada 
com uma cadeia de entrada de comprimento n. 
Deve-se considerar todas as computações possíveis para uma cadeia de entrada! 
Algumas considerações 
Cálculos em uma Máquina de Turing em tempo exponencial são bastante ineficientes e, 
portanto, raramente apresentam utilidade. 
Problemas para os quais não existe um algoritmo em tempo polinomial são ditos 
intratáveis. 
A teoria da complexidade classifica os problemas decidíveis em tratáveis e intratáveis. 
Exercício Resolvido 1: 
 Colocar em ordem crescente as seguintes complexidades: 
 n.log2(n), 3
10
; n
3
; n
1/3
 
Resposta: A ordem crescente é: 3
10
; n
1/3 
; nlog2(n); n
3
 . Observe-se a seguinte tabela 
n log2(n) n*log2(n) N
1/3
 n
3
 
1 0 0 1 1 
1000 9.97 9970 10 10
9
 
 Ainda, 3
10
 é o menor, pois trata-se de uma função constante. 
 
4 
 
Exercício Resolvido 2: Considere a seguinte afirmação: “Todo problema decidível 
apresenta solução com complexidade computacional polinomial.” A afirmação é 
verdadeira ou falsa? 
 Resposta: A afirmação é falsa. Diz-se que um problema é decidível se existe um 
algoritmo capaz de aceitar ou rejeitar, em tempo e espaço finitos, uma cadeia 
qualquer apresentada para análise. No entanto, o desempenho do algoritmo pode 
não ser polinomial, ou seja, pode ser de natureza combinatória, exponencial 
(confira na tabela 1, a coluna correspondente à função 2
n
). Uma máquina de 
Turing não-determinística - e portanto um algoritmo - apresenta a função de 
transição tal que para uma mesma combinação de estado corrente e de símbolo 
na fita de trabalho, é possível especificar múltiplas transições. Assim, em 
situações de não determinismos, deve-se considerar todas as computações 
possíveis para uma cadeia de entrada, o que pode resultar em desempenho de 
ordem combinatório ou exponencial. 
Referências 
Gersting, J. L. Fundamentos Matemáticos para a Ciência da Computação Rio de 
Janeiro: LTC, 2001. 
Lewis H. R. ; Papadimitrious, C. H. Elementos da Teoria da Computação Porto Alegre: 
Bookman, 2004. 
RAMOS, Marcus Vinicius Midena. NETO; João José. VEGA, Italo Santiago. 
Linguagens Formais. Teoria, Modelagem e Implementação Porto Alegre: Bookman, 
2009. 
ROSA, L. G. Linguagens Formais e Autômatos Rio de Janeiro: LTC, 2010.