Kích thước block tối ưu cho Jump Search là bao nhiêu? Hãy giải thích.
Kích thước block tối ưu cho Jump Search là bao nhiêu? Hãy giải thích.
Kích thước khối m tối ưu là √n.
Số phép so sánh tệ nhất: n/m (nhảy) + m − 1 (tuyến tính trong khối). Cực tiểu hoá f(m) = n/m + m: f'(m) = −n/m² + 1 = 0 ⇒ m = √n, khi đó f = 2√n − 1 ⇒ O(√n).
Đăng nhập để tham gia thảo luận cùng mọi người.
Chưa có bình luận nào
Hãy là người đầu tiên chia sẻ suy nghĩ của bạn.