Thời Gian Chạy O(log N)
Trong lĩnh vực lập trình và thuật toán, O(log N) là một thuật ngữ quen thuộc. Nhưng bạn đã bao giờ tự hỏi nguồn gốc của nó đến từ đâu? Bài viết này sẽ giúp bạn tìm hiểu chi tiết qua bài toán tìm kiếm nhị phân.
Giới Thiệu Về Tìm Kiếm Nhị Phân
Khi bạn có một mảng đã được sắp xếp với N phần tử và muốn tìm kiếm một giá trị cụ thể x, phương pháp tìm kiếm nhị phân là một cách rất hiệu quả. Thay vì kiểm tra từng phần tử trong mảng, bạn chỉ cần so sánh x với phần tử ở giữa mảng:
- Nếu
x == middle, bạn đã tìm thấy giá trị cần tìm. - Nếu
x < middle, bạn chỉ cần 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ụ Cụ Thể
Hãy xem xét trường hợp tìm kiếm giá trị 9 trong mảng đã sắp xếp {1, 5, 8, 9, 11, 13, 15, 19, 21}:
- So sánh 9 với 11 (phần tử giữa) -> 9 nhỏ hơn 11.
- Tìm kiếm 9 trong mảng
{1, 5, 8, 9, 11}. - So sánh 9 với 8 -> 9 lớn hơn 8.
- Tìm kiếm 9 trong mảng
{9, 11}. - So sánh 9 với 9 -> đã tìm thấy.
Tại Sao Thời Gian Chạy Là O(log N)?
Thời gian chạy O(log N) được xác định qua việc cắt giảm kích thước mảng sau mỗi lần so sánh. Ban đầu, bạn có mảng N phần tử, và mỗi bước so sánh giúp bạn giảm số phần tử còn lại xuống một nửa:
- Bước 1: N = 16 → N/2 = 8
- Bước 2: N/2 = 4
- Bước 3: N/2 = 2
- Bước 4: N/2 = 1
Số lượng bước cắt đôi này dẫn đến tổng số bước tìm kiếm là O(log N). Điều này có thể được diễn đạt qua công thức logarit:
- Nếu
2^k = N, bạn cần phải thực hiện k bước cắt đôi, tức là k = log2(N).
Ứng Dụng Trong Lập Trình
Thời gian chạy O(log N) không chỉ xuất hiện trong tìm kiếm nhị phân mà còn có mặt trong nhiều cấu trúc dữ liệu khác nhau, như cây tìm kiếm cân bằng (AVL trees, Red-Black trees). Mỗi khi bạn gặp vấn đề yêu cầu cắt đôi dữ liệu sau mỗi bước, hãy nhớ đến O(log N) vì nó thường đạt được kết quả tối ưu trong các thuật toán tìm kiếm.
Kết Luận
Biết cách nhận diện và vận dụng thời gian chạy O(log N) sẽ giúp bạn tối ưu hóa các thuật toán và cải thiện hiệu suất của chương trình. Hãy áp dụng kiến thức này vào các bài toán lập trình của bạn để thấy được sức mạnh của nó.
source: viblo
