Anonymous
0
0
Tìm chính xác số phép toán đơn cần thực hiện trong thuật toán tìm kiếm nhị phân
- asked 3 months agoVotes
0Answers
0Views
Giải Chuyên đề Tin học 11 Kết nối tri thức Bài 6: Ý tưởng và kĩ thuật chia để trị
Câu hỏi 1 trang 32 Chuyên đề Tin học 11:Tìm chính xác số phép toán đơn cần thực hiện trong thuật toán tìm kiếm nhị phân nếu dãy gốc chỉ có 1 phần tử
Lời giải:
Nếu n = 1, tức là left = right. Nếu A[left] = K thì sẽ thực hiện ngay các lệnh tại dòng 5 và dừng chương trình. Nếu A[left] ≠K thì sẽ gọi tiếp đệ quy tới các dòng 7 hoặc 9 nhưng sẽ trả về ngay –1. Vậy trong mọi trường hợp tổng số phép toán thực hiện khi n = 1 chỉ là hằng số, ta có T(1) = O(1).