Mostrar código-fonte de Trade-off Espaço-Tempo

Em [[ciência da computação]], especificamente em [[Teoria da computação|informática teórica]], se estuda o quanto de espaço em memória e tempo determinados algoritmos utilizam. Para fins didáticos e teóricos, muitos problemas são considerados solúveis, mas na prática tomariam bastante tempo para serem solucionados. Utiliza-se [[análise assintótica]], que "estipula" o quão rápido a quantidade de uso daquele recurso (tempo ou espaço, no contexto de computação) cresce em proporção ao crescimento do tamanho da entrada, para, dessa forma, comparar as soluções de um dado problema pelo potencial de complexidade, e não apenas casos isolados do uso destas soluções. O problema é que, na teoria, as [[Máquina de Turing|máquinas de Turing]] têm memória infinita, e consideramos que alguns processos genéricos são rápidos se durassem até um [[polinômio]] no tamanho da entrada, mas polinômio podem representar quantidades realmente grandes, e nossos recursos de memória em computadores são finitos. Daí a importância de se dosar a relação "espaço-tempo" de forma a se ter um [[trade-off]] entre essas duas grandezas e otimizar execução e resultado.

* '''Espaço''' se refere ao [[armazenamento de dados]] consumido na execução de um dado algoritmo, seja no armazenamento primário (e.g., na memória [[RAM]]) ou no armazenamento secundário (e.g., em um [[disco rígido]]). Em informática teórica, isto é analisado pelo ponto de visto de consumo (escrita, e não leitura) das células na(s) fita(s) de uma máquina de Turing. Um exemplo de conceito proveniente deste estudo é a definição de [[PSPACE]].
* '''Tempo''' se refere à quantidade de passos ao executar um algoritmo, tema estudado em [[complexidade de tempo]]. Esta análise se dá na observação do aumento do tempo para execução de um algoritmo de acordo com o tamanho da sua entrada, i.e., quanto maior sua entrada como se comporta em função do tempo o algoritmo.

Tanto na análise de complexidade de tempo e espaço existem métricas para se estudar vários casos. Essas métricas se dão pelo uso de notações como [[Grande-O]] e [[Complexidade caso médio|Complexidade do caso médio]].

''Trade-off'' '''espaço-tempo''' é um caso onde um [[algoritmo]] ou [[software]] compensa o aumento no consumo de memória levando menos tempo. A utilidade de um balanço entre espaço e tempo é afetado por custos fixos e variáveis, como velocidade da unidade de processamento, espaço na memória primária e secundária. Numa [[analogia]], é sujeito a [[Lei dos rendimentos decrescentes]] (em inglês, ''diminishing returns'').

== História ==
Na natureza, o uso do ''trade-off'' espaço-tempo pode ser encontrado nos primeiros estágios do [[Etologia|comportamento animal]]. O conhecimento adquirido e reações codificadas geneticamente evitam a necessidade de se "calcular" analiticamente este balanço em situações críticas. Mais especificamente para computadores, [[memorização]] tem sido implementada desde os mais antigos sistemas operacionais.

Em 1980 [[Martin Hellman]] propôs o uso de um ''trade-off'' espaço-tempo para [[Criptoanálise]].<ref>{{citar periódico|título=A Cryptanalytic Time-Memory Tradeoff |autor =Hellman, Martin |periódico=IEEE Transactions on Information Theory |data=julho de 1980 | volume=26 |número=4 |páginas=401–406 | doi=10.1109/tit.1980.1056220}}</ref>

== Tipos de tradeoff ==
=== Tabelas de busca vs. re-calculação ===
A situação mais comum é um algoritmo envolvendo um [[LUT|''Look-up-table'']], que é uma técnica utilizada no tratamento de imagens. Uma imagem pode ser representada por uma tabela de valores, e, a técnica de LUT é responsável pela tabela da imagem após o tratamento. Uma implementação pode incluir uma tabela inteira, que reduz o tempo computacional, mas aumenta a quantidade de memória necessária, ou pode-se computar partes das tabelas, aumentando o tempo, mas reduzindo o custo em memória.

=== Dados compactados vs. Dados descompactados ===
Um ''trade-off'' espaço-tempo pode ser aplicado ao problema de armazenamento de dados. Se dados são armazenados descompactados, utiliza-se mais espaço, porém menos tempo para ser utilizado do que se estiverem compactados. Pois a compactação de dados reduz o seu tamanho armazenado mas temos o custo adicional, ''over-head'', de rodar o algoritmo de descompactação de dados. Essa escolha depende de vários fatores, indo na raiz, no problema, pode depender das instancias, por exemplo, alguns algoritmos trabalham com dados compactados. Um exemplo deste caso é dos [[bitmap index|índices bitmap]], onde é mais rápido se trabalhar com dados compactados.

=== Re-renderização vs. imagens armazenadas ===
Armazenando apenas o código [[LaTex]] e renderizando isso como uma imagem várias vezes a página requisitada estaria trocando tempo for espaço; mais tempo usado, porém, menos espaço. Renderizando uma imagem quando a página é modificada e armazenando as imagens renderizadas seria uma troca de espaço por tempo; mais espaço usado, porém, menos tempo. Essa técnica é comumente conhecida como [[cache]].

=== Código menor vs. relaxamento de ''loop'' ===
Códigos grandes podem ser trocados por programas mais velozes quando aplicada a técnica de desaninhamento de ''loops''[[relaxamento de ''loop'']]. Essa técnica faz o código ficar mais para longo cada iteração de um dado ''loop'', mas salva o tempo computacional que seria utilizado em um controle de ''loop'' em cada iteração, ''i.e.'', reduzindo uma tarefa de cada iteração, a tarefa de verificar se aquele ''loop'' deve parar ou continuar. Claramente, esta técnica só pode ser utilizada em casos específicos, e há um ''trade-off'' entre espaço e tempo. Onde, neste caso, o espaço talvez não seja tão importante pelo fato de que normalmente os programas não ocuparem tanto espaço, mas compromete outros aspectos como a legibilidade.

== Outros exemplos ==
Algoritmos que também fazem  uso de ''trade-off'' espaço-tempo inclui:
* [[Passo-de-bebê passo-gigante]] ''Baby-step giant-step'', um algoritmo para calcular [[logaritmo discreto|logaritmos discretos]].
* [[Tabelas arco-ires]] ''Rainbow table'', em criptografia, numa situação onde o ''hacker'' quer fazer um ataque que seja mais rápido, menos custo de tempo computacional, que um [[ataque de força bruta]]. ''Rainbow Tables'' usam valores parcialmente pré-computados de ''hashes'' de uma [[Função de embaralhamento criptográfico|função de criptografia ''hash'']] para recuperar senhas, por exemplo. Decrescendo o tamanho da ''Rainbow table'' o tempo necessário para iterar sobre as alternativas aumenta.
* O [[ataque do homem no meio]], usa um ''trade-off'' espaço-tempo para encontrar a chave criptográfica em apenas
<math>2^{n+1}</math> encriptações (e <math>O(2^n)</math> de custo computacional de espaço) contra o esperado <math>2^{2n}</math> encriptações (mas apenas <math>O(1)</math> de custo computacional de espaço) de um ataque ingênuo.
* [[Programação dinânimca|Programação dinâmica]], onde a complexidade de tempo de um problema pode ser reduzido significantemente usando mais memória.

== Ver também ==
*
*
* [[Teorema da aceleração de Blum]]
* [[Teorema de Savitch]]

{{Referências}}

== Ligações externas ==
* [http://lasecwww.epfl.ch/pub/lasec/doc/Oech03.pdf Philippe Oechslin: Making a Faster Cryptanalytic Time-Memory Trade-Off.]
* [http://www.cs.sjsu.edu/faculty/stamp/RUA/TMTO.pdf Once Upon a Time-Memory Tradeoff.]

{{DEFAULTSORT:Trade-off Espaço-Tempo}}
[[Categoria:Otimização|Otimização de software]]