Tại sao việc sử dụng phương thức Array.prototype.includes() hoặc Array.prototype.indexOf() bên trong vòng lặp map() lại là một lỗi phổ biến về hiệu năng ở cấp độ Middle và cách tối ưu hóa bằng Hash Table là gì?

Question

Accepted Answer

Phân tích vấn đề
Phương thức includes() hoặc indexOf() có độ phức tạp O(N). Khi đặt chúng bên trong vòng lặp map() (vốn đã có độ phức tạp O(M)), tổng độ phức tạp của thuật toán sẽ trở thành O(M * N). Nếu M và N đều lớn, hiệu năng sẽ suy giảm nghiêm trọng, gây ra tình trạng treo trình duyệt hoặc quá tải CPU trên Server.
Giải pháp tối ưu
Sử dụng một cấu trúc dữ liệu trung gian như Set hoặc Hash Map để lưu trữ các phần tử cần kiểm tra. Việc tra cứu trong Set/Map có độ phức tạp trung bình là O(1).
Ví dụ minh họa
// O(M * N) - Kém hiệu quả
const result = listA.map(item => listB.includes(item));

// O(M + N) - Tối ưu
const setB = new Set(listB);
const result = listA.map(item => setB.has(item));
Lưu ý thực chiến
Luôn ưu tiên đánh đổi không gian lưu trữ (Space Complexity) để lấy tốc độ xử lý (Time Complexity) trong các bài toán xử lý dữ liệu lớn tại Enterprise.

Tại sao việc sử dụng phương thức Array.prototype.includes() hoặc Array.prototype.indexOf() bên trong vòng lặp map() lại là một lỗi phổ biến về hiệu năng ở cấp độ Middle và cách tối ưu hóa bằng Hash Table là gì?

Phân tích vấn đề

Làm Chủ Phỏng Vấn & Nâng Cao Trình Độ Chuyên Nghiệp

Tải Tuyển Tập 100+ Câu Hỏi Phỏng Vấn Chuyên Sâu (PDF)

Cần Mentor Phỏng Vấn Thử 1-1 & Tối Ưu CV?

Kiểm Tra CV Chuẩn ATS Miễn Phí

Câu hỏi big-o notation liên quan cùng chủ đề