Thời gian chạy O(log N)

Thời gian chạy O(log N)

Chúng ta thường gặp O(log N) trong các thuật toán. Nhưng nguồn gốc của nó từ đâu? Hãy cùng tìm hiểu qua bài toán tìm kiếm nhị phân.

Ví dụ tìm kiếm nhị phân:

Giả sử bạn có một mảng đã sắp xếp có N phần tử, và bạn muốn tìm một giá trị x trong đó. Thay vì kiểm tra từng phần tử, bạn so sánh x với phần tử ở giữa mảng:

• Nếu x == middle, bạn trả về.
• Nếu x < middle, bạn chỉ tìm kiếm nửa bên trái của mảng.
• Nếu x > middle, bạn tìm kiếm nửa bên phải của mảng.

Ví dụ:

• Tìm kiếm 9 trong mảng {1, 5, 8, 9, 11, 13, 15, 19, 21}:
  • So sánh 9 với 11 -> nhỏ hơn.
  • Tìm 9 trong mảng {1, 5, 8, 9, 11}.
  • So sánh 9 với 8 -> lớn hơn.
  • Tìm 9 trong mảng {9, 11}.
  • So sánh 9 với 9 -> tìm thấy.

Giải thích về O(log N)

• Ban đầu, chúng ta có một mảng N phần tử. Sau mỗi bước, chúng ta cắt số lượng phần tử còn lại còn một nửa:

  • N = 16 → N/2 = 8
  • N/2 = 4
  • N/2 = 2
  • N/2 = 1

• Với mỗi bước cắt đôi như vậy, số phần tử được giảm xuống một nửa, dẫn đến tổng số bước là O(log N).

Giải thích chi tiết:

• Giả sử N là số phần tử trong mảng. Mỗi lần so sánh, bạn cắt N xuống một nửa:

  • Nếu N = 16, bạn cắt làm đôi đến khi chỉ còn 1.

• Bây giờ, chúng ta có thể nhìn vào biểu thức logarit:

  • 2^k = N. Để tìm N, bạn cần bao nhiêu bước cắt đôi là log2(N).

Ứng dụng của O(log N)

• Các bài toán tìm kiếm nhị phân hay các cấu trúc dữ liệu như cây tìm kiếm cân bằng đều có thời gian chạy O(log N).
• Bất cứ khi nào bạn thấy vấn đề chia nửa dữ liệu mỗi lần, bạn sẽ nghĩ đến O(log N).