Khi xây dựng tính năng tìm kiếm tên người dùng trong một danh sách gồm một trăm nghìn bản ghi trên ứng dụng web, tại sao việc sử dụng thuật toán tìm kiếm tuần tự lại gây tắc nghẽn luồng Event Loop và Junior cần thay đổi cấu trúc dữ liệu hoặc thuật toán như thế nào để đạt độ phức tạp O(log N)?

Question

Accepted Answer

Trong các ứng dụng web hiện đại, việc thực hiện các vòng lặp nặng như Linear Search với độ phức tạp O(N) trên luồng chính của JavaScript sẽ làm chặn Event Loop, dẫn đến hiện tượng giật lag giao diện người dùng. Để giải quyết vấn đề này, lập trình viên Junior cần áp dụng các bước sau:

Bản chất vấn đề:

Linear Search kiểm tra từng phần tử một cách tuần tự, với một trăm nghìn phần tử, thời gian thực thi sẽ tăng tuyến tính, gây quá tải cho CPU.

Giải pháp tối ưu:

Sử dụng thuật toán Binary Search. Tuy nhiên, Binary Search yêu cầu mảng dữ liệu phải được sắp xếp từ trước.
Độ phức tạp thời gian của Binary Search là O(log N), nghĩa là với một trăm nghìn bản ghi, số lần lặp tối đa chỉ khoảng mười bảy lần thay vì một trăm nghìn lần.

Ví dụ code minh họa:
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;

while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (arr[mid] === target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}

4. Kinh nghiệm thực chiến tại Enterprise:
- Thay vì sắp xếp dữ liệu liên tục trên frontend, hãy thực hiện việc phân trang hoặc sắp xếp sẵn ở tầng Database, hoặc sử dụng Hash Map để đạt độ phức tạp O(1) nếu chỉ cần tra cứu chính xác tuyệt đối.

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ủ đề