4.1 Định nghĩa Memoization và những khái niệm chính
Memoization — là một kỹ thuật tối ưu hóa, trong đó kết quả của các hàm đắt đỏ được lưu trữ để tái sử dụng trong các lần gọi hàm tiếp theo với cùng tham số. Điều này giảm thiểu số lần tính toán lại, từ đó tăng hiệu suất.
Những khái niệm chính:
1. Caching:
Lưu trữ kết quả của hàm trong một số cấu trúc dữ liệu (ví dụ: từ điển hay mảng) để khi được gọi lại với các tham số giống nhau, kết quả đã lưu có thể được trả về mà không cần tính toán lại.
2. Bảng tra cứu (Lookup Table):
Cấu trúc dữ liệu được sử dụng để lưu trữ kết quả của những lần gọi hàm trước đó. Nó có thể là bảng băm (từ điển) hoặc mảng.
3. Gọi đệ quy:
Memoization cực kỳ hữu ích cho các hàm đệ quy, nơi mà cùng một bài toán con có thể được thực hiện nhiều lần với cùng tham số.
Độ phức tạp thời gian và không gian của các thuật toán tối ưu hóa:
Độ phức tạp thời gian:
Đối với nhiều bài toán đệ quy, memoization làm giảm độ phức tạp thời gian bằng cách giảm số lần tính toán lại. Ví dụ, tính số Fibonacci đệ quy có độ phức tạp thời gian là O(2^n), còn với memoization là O(n).
Độ phức tạp không gian:
Độ phức tạp không gian tăng lên do lưu trữ kết quả trong cache. Thông thường là O(n) cho các bài toán cần memoization.
Tóm tắt:
Memoization là một kỹ thuật mạnh mẽ để tối ưu hóa các thuật toán đệ quy, cho phép cải thiện đáng kể hiệu suất của chúng bằng cách giảm số lần tính toán lại.
Nó đặc biệt hữu ích cho những bài toán mà cùng một bài toán con được thực hiện nhiều lần với cùng tham số. Hiểu rõ khái niệm memoization và áp dụng nó trong thực tế giúp giải quyết hiệu quả những bài toán có độ phức tạp tính toán cao.
4.2 Ví dụ về tối ưu hóa
Ví dụ về tối ưu hóa các thuật toán đệ quy bằng cách sử dụng memoization
Ví dụ 1: Số Fibonacci
Thuật toán đệ quy tính số Fibonacci không dùng memoization có độ phức tạp thời gian dạng lũy thừa. Sử dụng memoization cải thiện đáng kể hiệu suất.
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]
# Ví dụ sử dụng:
print(fibonacci(10)) # Kết quả: 55
Quan trọng! Lưu ý rằng chúng ta sử dụng memo=None làm giá trị mặc định, và sau đó tạo từ điển rỗng bên trong hàm nếu memo không được truyền vào. Điều này giúp tránh vấn đề với đối tượng có thể thay đổi làm giá trị mặc định.
Ví dụ 2: Tổng tập con
Cần xác định xem có tập con nào của một tập hợp cho trước có tổng giá trị bằng với giá trị cho trước không.
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)]
# Ví dụ sử dụng:
arr = [3, 34, 4, 12, 5, 2]
sum_value = 9
n = len(arr)
print(is_subset_sum(arr, n, sum_value)) # Kết quả: True
Memoization thực chất là caching kết quả của các bài toán con.
Ví dụ, số Fibonacci F(10) == F(9) + F(8), nhưng để tính F(9), cần tính F(8) và F(7). Nghĩa là F(8) phải được tính hai lần: như là số hạng đầu tiên cho F(9) và như là số hạng thứ hai cho F(10). Để tránh việc tính toán nó hai lần, cần cache kết quả sau lần tính đầu tiên.
GO TO FULL VERSION