Tại sao việc sử dụng thuật toán tìm kiếm tuần tự (Linear Search) trên một mảng dữ liệu cấu hình gồm một trăm nghìn phần tử trong ứng dụng web lại gây hiện tượng chặn luồng Event Loop và giải pháp thuật toán nào đạt độ phức tạp O(log N)?

Question

Accepted Answer

1. Bản chất vấn đề
JavaScript chạy trên một luồng đơn (Single-threaded Event Loop). Khi thực hiện một vòng lặp nặng để tìm kiếm trên mảng $100.000$ phần tử mà không phân đoạn dữ liệu, luồng chính sẽ bị chiếm dụng hoàn toàn (Blocking Main Thread).
2. Phân tích độ phức tạp Big-O

Time Complexity: Thuật toán tìm kiếm tuần tự có độ phức tạp là $O(N)$. Với $N = 100.000$, số phép tính là tuyến tính nhưng nếu thực hiện liên tục trên mỗi thao tác gõ phím (Search Input), tổng số phép tính sẽ nhân lên rất lớn trong khoảng thời gian ngắn.

3. Giải pháp tối ưu hóa

Nếu dữ liệu đã được sắp xếp trước, hãy áp dụng thuật toán Binary Search với độ phức tạp thời gian là $O(\log N)$.
Nếu dữ liệu chưa sắp xếp và cần tìm kiếm liên tục, hãy lập chỉ mục (Indexing) bằng Hash Table để đạt độ phức tạp $O(1)$ cho việc tra cứu.

// Thuật toán Binary Search đạt O(log N)
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
Trong các tính năng Auto-complete hoặc Real-time Search tại Unicode Academy, Junior cần kết hợp debounce để giảm số lần gọi hàm, đồng thời chuẩn bị cấu trúc dữ liệu tối ưu thay vì duyệt mảng thô.

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