Bài toán :
Cho mảng gồm n phần tử đã được sắp xếp tăng dần và một phần tử x. Tìm xem x có trong mảng hay không? Nếu có x trong mảng thì trả ra kết quả là 1, nếu không trả ra kết quả là 0.
Dùng thuật toán tìm kiếm nhị phân,
Phân tích thuật toán :
Số x cho trước
+ Hoặc là bằng phần tử nằm ở vị trí giữa mảng
+ Hoặc là nằm ở nửa bên trái (x < phần tử ở giữa mảng )
+ Hoặc là nằm ở nửa bên phải (x > phần tử ở giữa mảng )
Mô tả thuật toán:
Input: mảng a[1..n]
Output: + 1 nếu x thuộc a
+ 0 nếu x không thuộc a
Từ nhận xét đó ta có giải thuật sau:
Đánh giá độ phức tạp thời gian của thuật toán
Trường hợp tốt nhất: Tương ứng với sự tìm được y trong lần so sánh đầu tiên, tức là x= a[giữa] (x nằm ở vị trí giữa mảng)
=> Ta có : Ttốt (n) = O(1)
Trường hợp xấu nhất: Độ phức tạp là O(log n)
Thật vậy, Nếu gọi T(n) là độ phức tạp của thuật toán, thì sau khi kiểm tra điều kiện ( x == a[giữa]) và sai thì gọi đệ qui thuật toán này với dữ liệu giảm nửa, nên thỏa mãn công thức truy hồi :
T(n) = 1 + T(n/2) với n>=2 và T(1) = 0
- Thiết kế và đánh giá thuật toán
- Lời nói đầu
- Bài 1: Thuật toán và độ phức tạp
- Bài 2:Phân tích thuật toán
- Bài 3: Cơ bản về thuật toán chia để trị
- Bài 4: Các bài toán sử dụng thuật toán chia để trị ( Divid and Conquer )
- Bài 5: Cơ bản về thuật toán Quay Lui (Back Tracking)
- Bài 6: Cơ bản về thuật toán nhánh cận và các bài toán
- Bài 7: Cơ bản về thuật toán Tham Lam
- Bài 8: Cơ bản về thuật toán Quy hoạch động
- Bài 9: Các bài toán sử dụng thuật toán Quy hoạch động
- Bài 10: Bài tập và tổng kết
- Tài liệu tham khảo