cách tính độ phức tạp thuật toán khác của giải thuật binary search

[himylove]

Hiện Himylove đang học phân tích thiết kế thuật toán và có nhận 1 bài về làm là :

ngoài cách phân tích sau còn có cách nào khác không ( hãy tìm ít nhất là 1 phương pháp khác ) :

Độ phức tạp thuật toán Binary Search

+ Nếu n=2r phần tử cần tìm ở đầu hoặc cuối danh sách hoặc r không nằm trong mảng cần tìm. Vì vậy với trường hợp này số lần chia nhiều nhất là r=log2n ( với r là số lần chia mảng ra làm đôi )
+Nếu n != 2r số nguyên r nhỏ nhất sao cho
2r-1 < n < 2r
<=> r-1< log2n<r
<=> r < log2n + 1 < r+1
=> số lần chia tối đa => danh sách gồm 1 phần tử không vượt quá r < log2n+ 1
Vậy big 0 của binary_search là log2n

cách này là cách của bạn đưa ra nhưng mà Himylove cũng không hiểu gì hết nhưng mà hỏi thầy thì thầy bảo lên mạng hỏi ^^!

( thầy có gợi ý là dùng cây phân tích - nhưng chả biết gì về cây phân tích cũng như không tìm được tài liệu gì liên quan tới cây phân tích nên mới lên đây hỏi vậy nếu có thể hãy chỉ cho Himylove cách phân tích thứ 2 và giải thích lun của cách giải thích của bạn nha ! cảm ơn nhiều nhiều )

[hacker_mubaohiem]

- Cái này chính là cây nhị phân đó bạn...Tuy nhiên thì phân tích đánh giá thuật toán liên quan đến Toán học nên rất khó chịu...Phải từ từ

[himylove]

- Cái này chính là cây nhị phân đó bạn...Tuy nhiên thì phân tích đánh giá thuật toán liên quan đến Toán học nên rất khó chịu...Phải từ từ

cảm ơn bạn đã hướng dẫn nhưng liệu bạn có thể nói rõ hơn được không dùng cây nhị phân để đánh giá độ phức tạp thế nào bạn có thể nói rõ được không

[Ada]

cảm ơn bạn đã hướng dẫn nhưng liệu bạn có thể nói rõ hơn được không dùng cây nhị phân để đánh giá độ phức tạp thế nào bạn có thể nói rõ được không

Khoan hãy nói tới độ phức tạp.

Có một danh sách gồm 8 phần tử. Chỉ dùng giấy bút, bạn hãy vẽ cây nhị phân mô tả thuật toán tìm kiếm binary cho danh sách này.

Gợi ý: đỉnh đầu tiên (gốc) của cây nhị phân được gán cho một giá trị là 8.

[himylove]

@Ada : như ada nói thì có khác gì trường hợp cây tìm kiếm nhị phân bị suy biến thành danh sách mà trở thành danh sách có khác gì trường hợp mà Himylove đang tìm hiểu

[Ada]

@Ada : như ada nói thì có khác gì trường hợp cây tìm kiếm nhị phân bị suy biến thành danh sách mà trở thành danh sách có khác gì trường hợp mà Himylove đang tìm hiểu

Bạn đừng suy đoán vội, cứ vẽ cây phân tích ra đi.

Cây phân tích biến thành danh sách ở thuật toán tìm kiếm tuần tự, nhưng không bao giờ là danh sách ở thuật toán tìm kiếm nhị phân.

[rox_rook]

Cậu kia tui cảm giác cậu hơi nhác, cây nhị phân là rất dễ rồi, chia 2, chia 2, chia 2.... Cái này toán học cơ bản thôi. Ada nói đúng rùi thì cậu chịu khó vẽ ra đi. Cậu xem với 8 phần tử cậu so sánh bao nhiều lần so sánh thì nó là độ phức tạp của BinaySearch thôi.

[himylove]

Có một danh sách gồm 8 phần tử. Chỉ dùng giấy bút, bạn hãy vẽ cây nhị phân mô tả thuật toán tìm kiếm binary cho danh sách này.

Gợi ý: đỉnh đầu tiên (gốc) của cây nhị phân được gán cho một giá trị là 8.

Himylove không hiểu rõ ý của ada là sao !
Cảm ơn nha ! lúc đầy Himylove nhầm lần giữa cây nhị phân và cây tìm kiếm nhị phân nên không vẽ được ra cây !
Bi h đọc kĩ mới làm được ! kết quả cũng cho ra thời gian tiêu tốn là log₂n giống như trong binary search ! cảm ơn bạn nhiều

Cậu kia tui cảm giác cậu hơi nhác, cây nhị phân là rất dễ rồi, chia 2, chia 2, chia 2.... Cái này toán học cơ bản thôi. Ada nói đúng rùi thì cậu chịu khó vẽ ra đi. Cậu xem với 8 phần tử cậu so sánh bao nhiều lần so sánh thì nó là độ phức tạp của BinaySearch thôi.

nếu chia 2 ra thì đây là cây nhị phân hay cây nhị phân tìm kiếm vậy bạn
Himylove nghĩ ở đây số lần duyệt để tìm số phần tử x mới chính là cái cần tìm chứ không phải số lần chia 2 rồi lại chia 2 như bạn đã nói ! ( Nếu sai thì nhớ reply để Himylove còn sửa nha )

[Ada]

Himylove không hiểu rõ ý của ada là sao !

Mình sẽ giải thích thêm ý mình. Thật ra bây giờ bạn đã giải ra rồi thì không cần giải thích nữa. Nhưng biết đâu sau này lại có bạn khác cần đến cây phân tích...

A. Cây phân tích nhị phân. Ở mỗi bài toán tìm 1 phần tử x trong một tập hợp S gồm |S| phần tử, ứng với mỗi thuật toán tìm chỉ thực hiện phép so sánh, có thể dựng một cây nhị phân mô tả thuật toán, như sau:

1. Mỗi đỉnh được đặt tên bằng một từ trên bảng chữ cái {0,1}:
1.1. Đỉnh đầu tiên (gốc) cây được đặt tên là từ rỗng (từ rỗng được ký hiệu là e).
1.2. Đỉnh nhánh bên trái và đỉnh nhánh bên phải (nếu có) của đỉnh v được đặt tên lần lượt là v0 và v1.

2. Mỗi đỉnh v được gán một số tự nhiên m(v):
2.1. m(v) = 1 nếu và chỉ nếu v là một đỉnh không có nhánh (lá).
2.2. m(v0) + m(v1) = m(v)

(Dễ thấy rằng m(v) bằng số lá của cây con có gốc là v, đặc biệt, m(e) = |S|.)

Mỗi chữ cái (bit) trong một từ v (ví dụ, v=000101001110) thể hiện một kết quả so sánh, 0 thể hiện "sai", 1 thể hiện "đúng". Từ v thể hiện một chuỗi kết quả so sánh. Số m(v) là số phần tử còn nghi vấn sau khi nhận được chuỗi kết quả v, m(v1) là số phần tử nghi vấn được chọn ra để thực hiện tiếp 1 phép so sánh nữa, còn m(v0) là số phần tử nghi vấn còn lại. Nói cách khác, thuật toán tìm ứng với cây nhị phân này sẽ có dạng:

Tham số:
x = giá trị cần tìm
S = phạm vi tìm kiếm

Tình trạng ban đầu:
v = chuỗi kết quả so sánh (= e), v ký hiệu gốc cây
s = tập hợp các phần tử nghi vấn (= S)
|s| = m(v) (= |S|)

while tồn tại đỉnh v1 và v0 loop
  từ tập hợp s, chọn tập hợp con s' sao cho |s'| = m(v1)
  thực hiện 1 phép so sánh để xác định x có thuộc s' hay không
  if có then
    s := s'
    v := v1
  else // không
    s := s - s'
    v := v0
  end if
end loop

Tình trạng cuối cùng:
v = chuỗi kết quả so sánh, v ký hiệu một lá của cây
s = tập hợp các phần tử nghi vấn
|s| = m(v) (= 1)


B. Bài toán ứng dụng cây phân tích nhị phân. Sếp của bạn sơ xuất để 1 chiếc nhẫn bằng vàng giả lẫn vào 12 chiếc nhẫn vàng thật. Bạn có nhiệm vụ đưa số nhẫn này ra thử tại ngân hàng để phát hiện chiếc nhẫn giả. Máy thử vàng của ngân hàng có thể thử một số vật bất kỳ để biết trong đó có vàng giả hay không nhưng nó không chỉ ra chính xác vật nào giả trong các vật đưa vào. Mỗi lần thử, ngân hàng thu lệ phí 20 000 đồng nếu máy trả lời là Có và 10 000 đồng nếu ngược lại. Bạn hãy tìm thuật toán thử vàng tối ưu.

[minhquan8338]

Không ai viết hoàn chỉnh một bài về độ phức tạp thuật toán tìm kiếm nhị phân ah`. Sao toàn viết tào lao thế này. Toàn đi sang chủ đề cây nhị phân là sao thế nhỉ .Nan~ quá đí :((