25:
224:
A space–time trade off can be applied to the problem of data storage. If data is stored uncompressed, it takes more space but access takes less time than if the data were stored compressed (since compressing the data reduces the amount of space it takes, but it takes time to run the
253:
every time the page is requested would be trading time for space; more time used, but less space. Rendering the image when the page is changed and storing the rendered images would be trading space for time; more space used, but less time. This technique is more generally known as
200:: an implementation can include the entire table, which reduces computing time, but increases the amount of memory needed, or it can compute table entries as needed, increasing computing time, but reducing memory requirements.
229:). Depending on the particular instance of the problem, either way is practical. There are also rare instances where it is possible to directly work with compressed data, such as in the case of compressed
270:. This technique makes the code longer for each iteration of a loop, but saves the computation time required for jumping back to the beginning of the loop at the end of each iteration.
168:. Using stored knowledge or encoding stimuli reactions as "instincts" in the DNA avoids the need for "calculation" in time-critical situations. More specific to computers,
380:
344:
410:
439:
302:
to crack passwords in minutes instead of weeks. Decreasing the size of the rainbow table increases the time required to iterate over the hash space.
49:
212:
data structures. Indexes improve the speed of lookup operations at the cost of additional space. Without indexes, time-consuming
67:
450:
576:
118:
299:
134:
469:
306:
294:
in cryptography, where the adversary is trying to do better than the exponential time required for a
40:
522:
475:
242:
484: – Something a computer needs needed to solve a problem, such as processing steps or memory
517:
481:
463:
349:
316:
385:
487:
447:, where the time complexity of a problem can be reduced significantly by using more memory.
282:
415:
8:
444:
153:
535:
310:
295:
286:
255:
35:
561:
556:
527:
226:
114:
103:
95:
539:
472: – Rules out assigning to arbitrary functions their computational complexity
246:
213:
130:
122:
267:
209:
176:
164:
Biological usage of time–memory tradeoffs can be seen in the earlier stages of
145:
570:
531:
291:
180:
490: – Relation between deterministic and nondeterministic space complexity
230:
197:
453:
which uses the space–time tradeoff with the additional parameter of data.
298:. Rainbow tables use partially precomputed values in the hash space of a
169:
233:, where it is faster to work with compression than without compression.
557:
Philippe
Oechslin: Making a Faster Cryptanalytic Time-Memory Trade-Off.
141:
266:
Larger code size can be traded for higher program speed when applying
508:
Hellman, Martin (July 1980). "A Cryptanalytic Time-Memory
Tradeoff".
106:
99:
165:
140:
The utility of a given space–time tradeoff is affected by related
172:
have been implemented since the very earliest operating systems.
278:
Algorithms that also make use of space–time tradeoffs include:
250:
208:
Database
Management Systems offer the capability to create
216:
operations are sometimes required to locate desired data.
149:
129:
refers to the time consumed in performing a given task (
418:
388:
352:
319:
478: – Amount of resources to perform an algorithm
219:
203:
433:
404:
374:
338:
261:
191:
236:
109:increased space usage with decreased time. Here,
568:
179:first proposed using a time–memory tradeoff for
507:
196:A common situation is an algorithm involving a
16:Algorithm trading more space for lower time
521:
152:speed, storage space), and is subject to
68:Learn how and when to remove this message
80:
510:IEEE Transactions on Information Theory
309:uses a space–time tradeoff to find the
569:
117:consumed in performing a given task (
186:
92:the algorithmic space-time continuum
18:
13:
14:
588:
562:Once Upon a Time-Memory Tradeoff.
550:
273:
466: – Property of an algorithm
451:Time/memory/data tradeoff attack
220:Compressed vs. uncompressed data
204:Database indexes vs. table scans
23:
262:Smaller code vs. loop unrolling
192:Lookup tables vs. recalculation
501:
428:
422:
369:
356:
237:Re-rendering vs. stored images
1:
494:
45:casual tone, lack of detail.
7:
457:
441:space) of the naive attack.
382:space) versus the expected
300:cryptographic hash function
43:. The specific problem is:
10:
593:
285:algorithm for calculating
159:
307:meet-in-the-middle attack
532:10.1109/tit.1980.1056220
476:Computational complexity
375:{\displaystyle O(2^{n})}
339:{\displaystyle 2^{n+1}}
227:decompression algorithm
482:Computational resource
470:Blum's speedup theorem
464:Algorithmic efficiency
435:
412:encryptions (but only
406:
405:{\displaystyle 2^{2n}}
376:
340:
249:and rendering it as a
577:Software optimization
436:
407:
377:
341:
88:time–memory trade-off
434:{\displaystyle O(1)}
416:
386:
350:
317:
283:Baby-step giant-step
84:space–time trade-off
50:improve this article
39:to meet Knowledge's
445:Dynamic programming
287:discrete logarithms
154:diminishing returns
98:is a case where an
431:
402:
372:
336:
296:brute-force attack
488:Savitch's theorem
346:encryptions (and
311:cryptographic key
241:Storing only the
187:Types of tradeoff
78:
77:
70:
41:quality standards
32:This article may
584:
544:
543:
525:
505:
440:
438:
437:
432:
411:
409:
408:
403:
401:
400:
381:
379:
378:
373:
368:
367:
345:
343:
342:
337:
335:
334:
96:computer science
86:, also known as
82:
73:
66:
62:
59:
53:
27:
26:
19:
592:
591:
587:
586:
585:
583:
582:
581:
567:
566:
553:
548:
547:
523:10.1.1.120.2463
506:
502:
497:
460:
417:
414:
413:
393:
389:
387:
384:
383:
363:
359:
351:
348:
347:
324:
320:
318:
315:
314:
276:
264:
239:
222:
214:Full table scan
206:
194:
189:
166:animal behavior
162:
74:
63:
57:
54:
47:
28:
24:
17:
12:
11:
5:
590:
580:
579:
565:
564:
559:
552:
551:External links
549:
546:
545:
516:(4): 401–406.
499:
498:
496:
493:
492:
491:
485:
479:
473:
467:
459:
456:
455:
454:
448:
442:
430:
427:
424:
421:
399:
396:
392:
371:
366:
362:
358:
355:
333:
330:
327:
323:
303:
292:Rainbow tables
289:
275:
274:Other examples
272:
268:loop unrolling
263:
260:
238:
235:
231:bitmap indices
221:
218:
210:Database index
205:
202:
193:
190:
188:
185:
177:Martin Hellman
170:look-up tables
161:
158:
146:variable costs
113:refers to the
76:
75:
31:
29:
22:
15:
9:
6:
4:
3:
2:
589:
578:
575:
574:
572:
563:
560:
558:
555:
554:
541:
537:
533:
529:
524:
519:
515:
511:
504:
500:
489:
486:
483:
480:
477:
474:
471:
468:
465:
462:
461:
452:
449:
446:
443:
425:
419:
397:
394:
390:
364:
360:
353:
331:
328:
325:
321:
312:
308:
304:
301:
297:
293:
290:
288:
284:
281:
280:
279:
271:
269:
259:
257:
252:
248:
244:
234:
232:
228:
217:
215:
211:
201:
199:
184:
182:
181:cryptanalysis
178:
173:
171:
167:
157:
155:
151:
147:
143:
138:
136:
135:response time
132:
128:
125:, etc.), and
124:
120:
116:
112:
108:
105:
101:
97:
93:
89:
85:
72:
69:
61:
51:
46:
42:
38:
37:
30:
21:
20:
513:
509:
503:
277:
265:
251:bitmap image
247:vector image
245:source of a
240:
223:
207:
198:lookup table
195:
174:
163:
139:
126:
115:data storage
110:
91:
87:
83:
79:
64:
55:
48:Please help
44:
33:
148:(of, e.g.,
131:computation
52:if you can.
495:References
58:March 2014
518:CiteSeerX
100:algorithm
571:Category
458:See also
313:in only
175:In 1980
133:time or
34:require
256:caching
160:History
104:program
36:cleanup
540:552536
538:
520:
107:trades
536:S2CID
142:fixed
111:space
305:The
144:and
127:time
528:doi
243:SVG
150:CPU
137:).
123:HDD
119:RAM
102:or
94:in
90:or
573::
534:.
526:.
514:26
512:.
258:.
183:.
156:.
121:,
542:.
530::
429:)
426:1
423:(
420:O
398:n
395:2
391:2
370:)
365:n
361:2
357:(
354:O
332:1
329:+
326:n
322:2
81:A
71:)
65:(
60:)
56:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.