Tìm số phép toán đơn cần thực hiện trong thuật toán trên nếu dãy có 2 phần tử

Tìm số phép toán đơn cần thực hiện trong thuật toán trên nếu dãy có 2 phần tử

Giải Chuyên đề Tin 11 Bài 6: Ý tưởng và kĩ thuật chia để trị - Kết nối tri thức

Câu hỏi 2 trang 32 Chuyên đề Tin học 11: Tìm số phép toán đơn cần thực hiện trong thuật toán trên nếu dãy có 2 phần tử

Lời giải:

Ta có công thức: T(n) = T(n/2) + O(1) và T(1) = O(1) = 1

Với n = 2 ta có T(2) = T(2/2) + O(1) = T(1) + O(1) = 1 + 1 = 2

Lời giải bài tập Chuyên đề Tin 11 Bài 6: Ý tưởng và kĩ thuật chia để trị hay, chi tiết khác:

• Khởi động trang 28 Chuyên đề Tin học 11: Trò chơi tìm bi giả ....

• Hoạt động 1 trang 28 Chuyên đề Tin học 11: 1. Hãy trình bày cách giải bài toán tìm bi giả với 5 viên bi ....

• Câu hỏi 1 trang 30 Chuyên đề Tin học 11: Với n = 9 bài toán tìm bi giả cần tối đa bao nhiêu lần cân ....

• Câu hỏi 2 trang 30 Chuyên đề Tin học 11: Mô tả bước "kết hợp" của bài toán 9 viên bi trên ....

• Hoạt động 2 trang 30 Chuyên đề Tin học 11: Quan sát lại một lần nữa thuật toán tìm kiếm nhị phân trên dãy các phần tử ....

• Câu hỏi 1 trang 31 Chuyên đề Tin học 11: Trong thuật toán tìm kiếm nhị phân trên, phần cơ sở là các lệnh nào? ....

• Câu hỏi 2 trang 31 Chuyên đề Tin học 11: Mô tả các bước thực hiện thuật toán tìm kiếm nhị phân khi ....

• Hoạt động 3 trang 31 Chuyên đề Tin học 11: Đọc, quan sát phân tích sau để biết được tính vượt trội của tìm kiếm nhị phân ....

• 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 ....

• Luyện tập 1 trang 32 Chuyên đề Tin học 11: Viết chương trình hoàn chỉnh nhập một dãy số đơn điệu tăng từ bàn phím ....

• Luyện tập 2 trang 32 Chuyên đề Tin học 11: Cho trước danh sách gồm có tên, điểm thi và được sắp xếp theo thứ tự ....

• Vận dụng 1 trang 32 Chuyên đề Tin học 11: Phương án không đệ quy của thuật toán tìm kiếm nhị phân có phải là ....

• Vận dụng 2 trang 32 Chuyên đề Tin học 11: Em hãy viết chương trình cài đặt các thuật toán tìm kiếm tuần tự và nhị phân ....

• Vận dụng 3 trang 32 Chuyên đề Tin học 11: Để tính giá trị (số nguyên) gần đúng căn bậc hai của số tự nhiên n cho trước ....