4.1 Defining Memoization and Its Key Concepts
Memoization is an optimization technique where the results of time-consuming functions are stored so they can be reused when the same inputs occur again. This reduces the number of repeated calculations, boosting performance.
Key Concepts:
1. Caching:
Storing function results in some data structure (like a dictionary or array) so that the results can be returned from storage instead of recomputing when the same inputs are encountered.
2. Lookup Table:
A data structure used for storing results of previous function calls. It can be a hash table (dictionary) or an array.
3. Recursive Calls:
Memoization is especially useful for recursive functions, where the same subproblems might be solved multiple times with identical parameters.
Time and Space Complexity of Optimized Algorithms:
Time Complexity:
For many recursive problems, memoization reduces time complexity by cutting down on repeated calculations. For instance, recursive Fibonacci calculation has time complexity of O(2^n), but with memoization, it's O(n).
Space Complexity:
Space complexity increases due to storing results in the cache, which is usually O(n) for problems requiring memoization.
Summary:
Memoization is a potent technique for optimizing recursive algorithms, greatly enhancing their performance by reducing the number of repeated calculations.
It is particularly beneficial for problems where the same subproblems are solved repeatedly with identical parameters. Understanding the concepts of memoization and applying it in practice allows for efficiently tackling computationally heavy problems.
4.2 Optimization Examples
Examples of optimizing recursive algorithms using memoization
Example 1: Fibonacci Numbers
The recursive algorithm for computing Fibonacci numbers without memoization has exponential time complexity. Using memoization significantly boosts performance.
def fibonacci(n, memo=None):
if memo is None:
memo = {}
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
return memo[n]
# Example usage:
print(fibonacci(10)) # Output: 55
Important! Note that we use
memo=None as the default argument, and then create an empty dictionary inside the function if memo isn't passed. This avoids problems with mutable default arguments.
Example 2: Subset Sum
Determine if there exists a subset of a given set whose sum of elements equals a given value.
def is_subset_sum(arr, n, sum_value, memo=None):
if memo is None:
memo = {}
if (n, sum_value) in memo:
return memo[(n, sum_value)]
if sum_value == 0:
return True
if n == 0 and sum_value != 0:
return False
if arr[n - 1] > sum_value:
memo[(n, sum_value)] = is_subset_sum(arr, n - 1, sum_value, memo)
return memo[(n, sum_value)]
memo[(n, sum_value)] = is_subset_sum(arr, n - 1, sum_value, memo) or is_subset_sum(arr, n - 1, sum_value - arr[n - 1], memo)
return memo[(n, sum_value)]
# Example usage:
arr = [3, 34, 4, 12, 5, 2]
sum_value = 9
n = len(arr)
print(is_subset_sum(arr, n, sum_value)) # Output: True
Memoization is essentially caching the results of subproblems.
For example, Fibonacci number F(10) == F(9) + F(8), but to calculate F(9), we need to compute F(8) and F(7). So, we need to compute F(8) twice: as the first term for F(9) and as the second term for F(10). To avoid calculating it twice, we need to cache it after the first computation.
GO TO FULL VERSION