Trong quá trình xử lý dữ liệu giỏ hàng, việc kiểm tra xem một mặt hàng đã tồn tại trong mảng giỏ hàng hay chưa bằng phương thức Array.prototype.includes dẫn đến độ phức tạp nào và cấu trúc dữ liệu nào giúp giảm độ phức tạp xuống O(1)?

Question

Accepted Answer

1. Bản chất vấn đề
Junior thường sử dụng phương thức cart.includes(item) hoặc cart.findIndex(item => item.id === targetId) bên trong một vòng lặp để kiểm tra sự tồn tại của sản phẩm. Phương thức này thực hiện tìm kiếm tuần tự (Linear Search).
2. Phân tích độ phức tạp Big-O

Nếu thực hiện kiểm tra cho từng sản phẩm trong một danh sách có $M$ phần tử đối với giỏ hàng có $N$ phần tử, Time Complexity sẽ là $O(N 	imes M)$.
Nếu danh sách giỏ hàng lớn, hiệu năng sẽ suy giảm nghiêm trọng theo hàm bậc hai hoặc tuyến tính nặng nề.

3. Giải pháp tối ưu hóa
Thay vì sử dụng mảng (Array) thuần túy, chúng ta nên sử dụng Set hoặc Map trong JavaScript để lưu trữ các định danh (id) sản phẩm.
// Sử dụng Set để kiểm tra sự tồn tại với O(1)
const cartSet = new Set();
cartSet.add('prod_123');

// Kiểm tra tồn tại
const exists = cartSet.has('prod_123'); // O(1)
4. Kinh nghiệm thực chiến
Trong kiến trúc Frontend hiện đại, khi xây dựng các ứng dụng thương mại điện tử lớn, việc chuyển đổi cấu trúc dữ liệu từ Array sang Map hoặc Set cho các state quản lý giỏ hàng giúp các thao tác kiểm tra, thêm, xóa đạt độ phức tạp tối ưu $O(1)$, giữ cho ứng dụng luôn mượt mà.

1. Bản chất 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ủ đề