Từ 1 tới 6 trên tổng số 6 kết quả

Đề tài: tìm số phép toán cơ bản nhiều nhất và độ phức tạp tiệm cận của thuật toán binarySearch

  1. #1
    Ngày gia nhập
    05 2011
    Nơi ở
    hà nội
    Bài viết
    5

    Mặc định tìm số phép toán cơ bản nhiều nhất và độ phức tạp tiệm cận của thuật toán binarySearch

    Mọi người ơi, giúp mình tính số phép toán cơ bản nhiều nhất và độ phức tạp tiệm cận của thuật toán BinarySeach này với.Cảm ơn mọi người nhiều nha
    thuật toán:
    int BinarySearch(int a[],int N,int x )
    {
    int left =0, right = N-1, midle;
    while (left <= right)
    {
    mid = (left + right)/2;
    if (x == a[midle])
    return midle;
    if (x<a[midle])right = midle -1;
    else left = midle +1;
    }
    return -1;
    }

  2. #2
    Ngày gia nhập
    10 2011
    Bài viết
    552

    Cái này thì xin mời đọc tài liệu. Người ta đã viết rất kĩ và chi tiết.
    Độ phức tạp cực đại, cực tiểu, trung bình của Bin Search... blah blah.
    Ko có lý gì giờ phải copy cái đống tài liệu kia rồi past vào đây cả
    Ko hiểu chỗ nào thì hỏi rồi trả lời mới đc, hỏi nguyên cái thế này khác nào bảo "anh tìm sách giùm tui" @@ ??
    Um Mani Padme Hum...!!

  3. #3
    Ngày gia nhập
    05 2011
    Nơi ở
    hà nội
    Bài viết
    5

    Trích dẫn Nguyên bản được gửi bởi clchicken Xem bài viết
    Cái này thì xin mời đọc tài liệu. Người ta đã viết rất kĩ và chi tiết.
    Độ phức tạp cực đại, cực tiểu, trung bình của Bin Search... blah blah.
    Ko có lý gì giờ phải copy cái đống tài liệu kia rồi past vào đây cả
    Ko hiểu chỗ nào thì hỏi rồi trả lời mới đc, hỏi nguyên cái thế này khác nào bảo "anh tìm sách giùm tui" @@ ??
    đây là đề thi của bọn mình, thật sự thì mình cũng không biết là để giải nó lại cần phải copy cả đống tài liệu đâu. Mình chỉ muốn hỏi cách tính số phép toán mà chủ yếu là các phép toán trong vòng while ấy, bạn có thể giúp mình được không. Mình đã thi rồi, giờ mình chỉ muốn tìm hiểu thêm thui

  4. #4
    Ngày gia nhập
    10 2011
    Bài viết
    552

    Bài này ko thể dùng cách Đếm phép toán tích cực được mà phải dùng pp "Master Theorem" để tính độ phức tạp.
    Bạn biểu diễn cái đó ra = Truy hồi hay Đệ quy thì sẽ thấy rõ ràng và dễ lý luận hơn.
    Um Mani Padme Hum...!!

  5. #5
    Ngày gia nhập
    09 2009
    Nơi ở
    Hoa sơn tuyệt đỉnh
    Bài viết
    407

    Số lần lặp tối đa là log2(n)+1.
    Độ phức tạp là O(logn)

    my houses
    my school
    tỐnG lÊ cHâN mAnG kỶ nIệM bUồN cHo AnH...

  6. #6
    Ngày gia nhập
    05 2011
    Nơi ở
    hà nội
    Bài viết
    5

    Mặc định tìm số phép toán cơ bản nhiều nhất và độ phức tạp tiệm cận của thuật toán binarySearch

    nhưng cái chỗ log2n+1 ấy là số phép toán ứng với câu lệnh nào hả bạn, bạn chỉ rõ hơn mình với

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

  1. Thuật toán tìm 1 tên mà nhiều người trùng nhất trong danh sách n người.
    Gửi bởi Mr.Kutjs trong diễn đàn Nhập môn lập trình C#, ASP.NET
    Trả lời: 6
    Bài viết cuối: 24-09-2012, 08:56 AM
  2. Giảm thuế thu nhập doanh nghiệp năm 2011, miễn thuế thu nhập cá nhân đến hết năm 2012
    Gửi bởi tailanh8423 trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 0
    Bài viết cuối: 28-05-2012, 01:10 PM
  3. thuật toán ghi nhạc lên đĩa CD sao cho số bài hát ghi được là nhiều nhất?
    Gửi bởi tamtn trong diễn đàn Thắc mắc CTDL & Giải thuật
    Trả lời: 2
    Bài viết cuối: 17-05-2012, 10:54 PM
  4. Cập nhật nhiều Gridview vào nhiều datatable trong Dataview
    Gửi bởi MYNAM trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 0
    Bài viết cuối: 10-07-2011, 12:08 PM
  5. quicksort && binarysearch với nhiều phần tử
    Gửi bởi ngoctrungbmt trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 0
    Bài viết cuối: 11-03-2011, 10:49 PM

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