시공간의 트레이드오프
Space–time tradeoff |
컴퓨터 공학에서 공간-시간 트레이드오프 또는 시간-기억 트레이드오프는 알고리즘 또는 프로그램이 시간 감소와 공간 사용 증가를 교환하는 경우입니다.여기서 공간은 주어진 작업(RAM, HDD 등)을 수행하는 데 소비되는 데이터 스토리지를 의미하며, 시간은 주어진 작업(연산 시간 또는 응답 시간)을 수행하는 데 소비되는 시간을 의미합니다.
주어진 시공간의 트레이드오프의 효용성은 관련 고정비용 및 가변비용(예: CPU 속도, 스토리지 공간)의 영향을 받으며 수익률이 감소할 수 있습니다.
역사
시간-기억 트레이드오프의 생물학적 사용은 동물 행동의 초기 단계에서 볼 수 있다.저장된 지식을 사용하거나 자극 반응을 DNA에서 "인스턴트"로 인코딩하는 것은 시간적으로 중요한 상황에서 "계산"의 필요성을 피합니다.컴퓨터에 특화된 룩업 테이블은 초창기 [citation needed]운영체제부터 구현되어 왔습니다.
1980년에 Martin Hellman은 암호 [1]분석에 시간-메모리 트레이드오프를 사용할 것을 처음 제안했습니다.
트레이드오프 유형
룩업 테이블과 재계산
일반적인 상황은 룩업 테이블을 포함하는 알고리즘입니다.실장에서는 테이블 전체를 포함할 수 있기 때문에 컴퓨팅 시간은 단축되지만 필요한 메모리 양은 증가하거나 필요에 따라 테이블 엔트리를 계산할 수 있기 때문에 컴퓨팅 시간은 증가하지만 메모리 요건은 감소합니다.
압축된 데이터와 압축되지 않은 데이터 비교
데이터 스토리지 문제에 시공간의 트레이드오프를 적용할 수 있습니다.데이터를 압축하지 않고 저장하는 경우 데이터를 압축한 경우보다 더 많은 공간이 필요하지만 액세스 시간은 더 적게 소요됩니다(데이터를 압축하면 필요한 공간은 줄어들지만 압축 해제 알고리즘을 실행하는 데는 시간이 걸립니다).문제의 특정 예에 따라 어느 방법이든 실용적입니다.압축된 비트맵 인덱스의 경우처럼 압축되지 않은 경우보다 압축된 데이터를 직접 사용할 수 있는 드문 경우도 있습니다.
이미지 재렌더와 저장된 이미지 비교
벡터 이미지의 SVG 소스만 저장하고 페이지가 요청될 때마다 비트맵 이미지로 렌더링하는 것은 시간과 공간을 교환하는 것입니다. 시간은 더 많이 사용되지만 공간은 더 적게 사용됩니다.페이지가 변경될 때 이미지를 렌더링하고 렌더링된 이미지를 저장하는 것은 시간과 교환할 수 있는 공간이 됩니다. 사용 공간은 늘어나지만 시간은 줄어듭니다.이 기술은 일반적으로 캐싱으로 알려져 있습니다.
더 작은 코드와 루프 풀림
루프 언롤링을 적용할 때 코드 사이즈가 클수록 프로그램 속도가 빨라집니다.이 기술은 루프의 각 반복에 대해 코드를 더 길게 만들지만 각 반복이 끝날 때 루프의 선두로 점프하는 데 필요한 계산 시간을 절약합니다.
기타 예
공간-시간 트레이드오프를 활용하는 알고리즘은 다음과 같습니다.
- 이산 로그를 계산하기 위한 초기 단계 거대 단계 알고리즘
- 레인보우 테이블은 암호화로, 상대방이 무차별 공격에 필요한 기하급수적인 시간보다 더 잘 처리하려고 합니다.레인보우 테이블은 암호화 해시 함수의 해시 공간에서 부분적으로 미리 계산된 값을 사용하여 암호를 몇 주가 아닌 몇 분 만에 해독합니다.무지개 테이블의 크기를 줄이면 해시 공간에서 반복하는 데 필요한 시간이 늘어납니다.
- 미트인더미들 공격에서는 시공간 트레이드오프를 사용하여 암호화 키를 합니다.2 n + (및 (n) \ ( { )스페이스에서2 (2 n )스페이스에서2 n ( n )암호화(단 O ( 에서만).공략.
- 동적 프로그래밍: 더 많은 메모리를 사용함으로써 문제의 시간 복잡성을 크게 줄일 수 있습니다.
「 」를 참조해 주세요.
레퍼런스
- ^ Hellman, Martin (July 1980). "A Cryptanalytic Time-Memory Tradeoff". IEEE Transactions on Information Theory. 26 (4): 401–406. CiteSeerX 10.1.1.120.2463. doi:10.1109/tit.1980.1056220.
