Trang 1 trên tổng số 2 12 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 14 kết quả

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

  1. #1
    Ngày gia nhập
    11 2007
    Bài viết
    17

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

    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 )

  2. #2
    Ngày gia nhập
    03 2008
    Bài viết
    78

    - 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ừ
    No way, No success..

  3. #3
    Ngày gia nhập
    11 2007
    Bài viết
    17

    Trích dẫn Nguyên bản được gửi bởi hacker_mubaohiem Xem bài viết
    - 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

  4. #4
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất nhiều sóng gió
    Bài viết
    447

    Trích dẫn Nguyên bản được gửi bởi himylove Xem bài viế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
    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.

  5. #5
    Ngày gia nhập
    11 2007
    Bài viết
    17

    @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

  6. #6
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất nhiều sóng gió
    Bài viết
    447

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

    Trích dẫn Nguyên bản được gửi bởi himylove Xem bài viết
    @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.

  7. #7
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    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.

  8. #8
    Ngày gia nhập
    11 2007
    Bài viết
    17

    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à log2n 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 )
    Attached Thumbnails Attached Thumbnails day.jpg  
    Đã được chỉnh sửa lần cuối bởi himylove : 15-05-2008 lúc 12:14 AM.

  9. #9
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất nhiều sóng gió
    Bài viết
    447

    Trích dẫn Nguyên bản được gửi bởi himylove Xem bài viết
    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|)
    Code:
    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.
    Đã được chỉnh sửa lần cuối bởi Ada : 16-05-2008 lúc 08:00 AM.

  10. #10
    Ngày gia nhập
    05 2008
    Bài viết
    20

    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á đí :((

Các đề tài tương tự

  1. Lý thuyết đồ thị | Giải thuật DFS (Depth First Search)
    Gửi bởi vie_kainznz trong diễn đàn Thủ thuật, Tutorials CTDL & Giải thuật
    Trả lời: 1
    Bài viết cuối: 14-01-2013, 10:48 PM
  2. Hàm insert giảm dần trong binary search tree
    Gửi bởi sieuthanh trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 1
    Bài viết cuối: 13-11-2011, 12:55 AM
  3. Tài liệu lập trình C Tài liệu tiếng việt về thuật toán Harmony Search ở đâu ?
    Gửi bởi ncccrazy trong diễn đàn Tài liệu, ebooks và công cụ
    Trả lời: 0
    Bài viết cuối: 13-04-2011, 06:14 PM
  4. binary search bị lỗi , fix hộ mình với
    Gửi bởi c4u.ng0c trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 6
    Bài viết cuối: 27-12-2010, 09:55 PM
  5. Thuật toán binary search tree trong lập trình C
    Gửi bởi kingdark115 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 4
    Bài viết cuối: 05-12-2007, 01:04 AM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn