Sẽ có bao nhiêu phép so sánh tìm kiếm nhị phân trong trường hợp xấu nhất khi sử dụng thuật toán này?

Question

Chào bạn dưới đây là mã giả để thực hiện tìm kiếm nhị phân của tôi:

Input: (A[0...n-1], K) 
begin 
    l ← 0; r ← n-1 
    while l ≤ r do 
     m ← floor((l+r)/2) 
     if K > A[m] then l ← m+1 
     else if K < A[m] then r ← m-1 else return m 
     end if 
    end while 
    return -1 // key not found 
end 

Tôi chỉ tự hỏi làm thế nào để tính toán số lượng so sánh thực hiện này sẽ thực hiện trong trường hợp xấu nhất cho một mảng được sắp xếp kích thước n?

Số lượng so sánh có = lg n + 1 không? hay cái gì khác?

Answer 1

Các trường hợp xấu nhất trong trường hợp này là, nếu các yếu tố K là không có mặt trong A và nhỏ hơn so với tất cả các yếu tố trong A. Sau đó, chúng ta có hai sự so sánh trong mỗi bước: K > A[m] và K < A[m].

Đối với mỗi bước, mảng được cắt thành hai phần, mỗi phần có kích thước (n-1)/2, chúng tôi có tối đa là log_2(n-1) bước.

Điều này dẫn đến tổng số các so sánh là 2*log_2(n-1), tương đương với thực tế là O(log(n)).

Answer 2

Theo trang wikipedia trên binary search, hiệu suất trường hợp xấu nhất của thuật toán này là O(lg n), đo lường số lượng so sánh tiệm cận cần thiết. Số thực hiện thực tế là so với trường hợp xấu nhất sẽ là 2*lg(n-1), như đã được chỉ ra trong câu trả lời của @ hielsnoppe.

Các giả trong câu hỏi thể hiện việc thực hiện điển hình của một tìm kiếm nhị phân, do đó sự phức tạp thực hiện dự kiến ​​tổ chức cho một mảng (hay vector) kích thước n:

• hiệu suất Trường hợp tốt nhất: O(1)
• Trung bình hiệu suất trường hợp: O(lg n)
• hiệu suất trường hợp xấu nhất: O(lg n)

Mở kiểm tra chặt chẽ hơn, có hai vấn đề với giả trong câu hỏi:

• Dòng: if K > A[m] then return l ← m+1 nên đọc if K > A[m] then l ← m+1. Bạn không thể quay lại được
• Dòng: m ← floor((l+r)/2) có thể gây tràn nếu số đủ lớn khi làm việc với số nguyên có kích thước cố định. Cú pháp chính xác khác nhau tùy thuộc vào ngôn ngữ lập trình thực tế bạn đang sử dụng, nhưng một cái gì đó dọc theo điều này sẽ khắc phục sự cố: m ← (l + r) >>> 1, trong đó >>> là toán tử thay đổi bên phải chưa ký. Đọc thêm về sự cố trong here.

Answer 3

Một sự điều chỉnh rất nhỏ để hielsnoppe's answer:

Trong một mảng -element n (n > 0), yếu tố để so sánh là chỉ số m = floor((n-1)/2). Vì vậy, có ba khả năng

1. A[m] < K, sau đó sau khi so sánh, tìm kiếm tiếp tục trong một mảng kết nối n-1-m = ceiling((n-1)/2).
2. A[m] > K, sau đó sau hai lần so sánh, tìm kiếm tiếp tục trong một mảng kết nối m.
3. A[m] == K, sau đó chúng tôi hoàn thành sau hai lần so sánh.

Vì vậy, nếu chúng ta biểu thị tối đa (trường hợp xấu nhất) số so sánh cho một tìm kiếm trong một mảng -element n bởi C(n), chúng tôi có

C(0) = 0 
C(n) = max { 1 + C(ceiling((n-1)/2), 2 + C(floor((n-1)/2) }, n > 0 

Đối lẻ n = 2k+1, sàn và trần nhà là giống hệt nhau, do đó tối đa là rõ ràng sau này,

C(2k+1) = 2 + C(k) 

và thậm chí n = 2k, chúng tôi tìm

C(2k) = max { 1 + C(k), 2 + C(k-1) }. 

Đối n = 2, mà giải quyết để C(2) = 1 + C(1) = 1 + 2 = 3, cho tất cả lớn hơn thậm chí n, tối đa là 2 + C(k-1), vì đối với n >= 1 chúng tôi có C(n) <= C(n+1) <= C(n) + 1.

Đánh giá đệ quy cho là người đầu tiên vài n, chúng tôi tìm

C(0) = 0 
C(1) = 2 
C(2) = 3 
C(3) = C(4) = 4 
C(5) = C(6) = 5 
C(7) = C(8) = C(9) = C(10) = 6 
C(11) = ... = C(14) = 7 
C(15) = ... = C(22) = 8 
C(23) = ... = C(30) = 9 

Vì vậy, bằng cảm ứng, chúng tôi chứng minh

C(n) = 2k, if 2^k <= n+1 < 2k + 2^(k-1), and 
C(n) = 2k+1, if 2^k + 2^(k-1) <= n+1 < 2^(k+1) 

hoặc

C(n) = 2*log2(n+1) + floor(2*(n+1)/(3*2^floor(log2(n+1)))). 

Đây là một chính xác trên ràng buộc.