Chiến lược tối ưu hóa bằng bảng băm¶

Trong các bài toán thuật toán, chúng ta thường giảm độ phức tạp thời gian của thuật toán bằng cách thay thế tìm kiếm tuyến tính bằng tìm kiếm bằng bảng băm. Hãy cùng sử dụng một bài toán thuật toán để hiểu sâu hơn về điều này.

Question

Cho một mảng số nguyên nums và một giá trị mục tiêu target, hãy tìm hai phần tử trong mảng có tổng bằng target và trả về chỉ số của chúng. Bất kỳ kết quả nào thỏa mãn đều được chấp nhận.

Tìm kiếm tuyến tính: Đánh đổi thời gian lấy không gian¶

Xét phương án duyệt trực tiếp qua tất cả các cặp kết hợp có thể. Như minh họa trong hình dưới đây, chúng ta sử dụng các vòng lặp lồng nhau và kiểm tra xem tổng của hai số nguyên có bằng target hay không ở mỗi lượt lặp. Nếu có, ta trả về chỉ số của chúng.

Mã nguồn được hiển thị bên dưới:

[file]{two_sum}-[class]{}-[func]{two_sum_brute_force}

Phương pháp này có độ phức tạp thời gian là \(O(n^2)\) và độ phức tạp không gian là \(O(1)\), do đó sẽ rất tốn thời gian khi kích thước dữ liệu đầu vào lớn.

Tìm kiếm bằng bảng băm: Đánh đổi không gian lấy thời gian¶

Xét phương án sử dụng một bảng băm với các khóa (key) là các phần tử của mảng và giá trị (value) là chỉ số tương ứng của chúng. Duyệt qua mảng và thực hiện các bước như hình minh họa dưới đây trong mỗi lượt lặp:

Kiểm tra xem số target - nums[i] đã có trong bảng băm chưa. Nếu có, trả về ngay chỉ số của hai phần tử này.
Thêm cặp khóa-giá trị nums[i] và chỉ số i vào bảng băm.

<1><2><3>

Cách triển khai được trình bày dưới đây và chỉ yêu cầu một vòng lặp đơn:

[file]{two_sum}-[class]{}-[func]{two_sum_hash_table}

Phương pháp này giảm độ phức tạp thời gian từ \(O(n^2)\) xuống \(O(n)\) thông qua việc tìm kiếm bằng bảng băm, giúp cải thiện đáng kể hiệu suất thời gian chạy.

Vì cần duy trì thêm một bảng băm phụ trợ nên độ phức tạp không gian là \(O(n)\). Mặc dù vậy, phương pháp này mang lại sự đánh đổi thời gian - không gian tổng thể cân bằng hơn, biến nó thành lời giải tối ưu cho bài toán này.