[알고리즘] 타뷸레이션(Tabulation)

타뷸레이션(Tabulation)의 정의와 메모이제이션(Memoization)과의 차이

타뷸레이션(Tabulation)이란?

1. 동일한 계산을 반복해야 할 경우 한 번 계산한 결과를 메모리에 저장해 두었다가 재사용하여 중복 계산을 방지할 수 있게 하는 기법이다.

2. 중복 계산을 방지하여 전체 실행 속도를 빠르게 한다.

3. 앞으로 계산할 모든 값에 대해 저장하여 초기화 오버헤드가 크다.

4. 초기화 이후에 계산해둔 값을 사용할 때 더 이상의 계산이 필요하지 않다.

5. Table + ulation으로 테이블에 미리 값을 적어놓는다고 생각하자.

 

차이점

1. 메모이제이션과 비슷하지만, 값을 미리 계산해둔다는 차이점이 있다.

2. 메모이제이션 결과가 필요해질 때 계산한다.(Lazy-Evaluation)

 - 필요한 값의 요청이 들어올 때 이전에 계산해둔 값이 있다면 그 값을 사용하고 없다면 새로 계산한다.

 - memoization을 활용하여 값을 계산할 경우 시간 복잡도는 O(n)이다.

3. 타뷸레이션은 필요하지 않은 값도 미리 계산해둔다(Eager-Evaluation)는 차이가 있다.

 - 이전에 계산해둔 값이 있다면 그 값을 사용하고 없다면 새로 계산하는 방식으로 초기화할 때 범위에 해당하는 모든 값을 계산한다. 

 - 초기화 오버헤드가 있지만 일단 계산해둔 값은 시간복잡도가 상수 시간(O(1))이 된다.

 

메모이제이션이란?

2023.06.13 - [개발 용어 정리] - [알고리즘] 메모이제이션(memoization)

[알고리즘] 메모이제이션(memoization)