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

Đề tài: Chứng minh độ phức tạp của các thuật toán trong C

  1. #1
    Ngày gia nhập
    05 2014
    Bài viết
    3

    Mặc định Chứng minh độ phức tạp của các thuật toán trong C

    Em đang học Lý thuyết về giải thuật. Trong quá trình học có phần đánh giá độ phức tạp của thuật toán. Nhưng em cần chứng minh lại. Mọi người có thể giúp em được không ạ.

    Chứng minh độ phức tạp của các thuật toán sau:
    a. Tìm kiếm tuyến tính (Linear Search)
    T(n) = O(n)

    b. Tìm kiếm nhị phân (Binary Search)
    1. Xấu nhất: log2n
    2. Trung bình: log2(n/2)

    c. Sắp xếp cây với giá trị MIN (Heap-MIN)
    T = nlog2n

    d. Sắp xếp theo phân hoạch dãy (Quick Sort)
    1. Xấu nhất: n2
    2. Trung bình: n*log(n)

    e. Sắp xếp theo trộn trực tiếp (Merge Sort)
    T = nlog2n

    Xin cảm ơn mọi người

  2. #2
    Ngày gia nhập
    01 2013
    Bài viết
    1,479

    a với b, c, d1, e thì tìm công thức dạng T(n)=T(...)+O(...) rồi khai triển.
    d2 thì bạn nên xem trên Wiki, không dễ đâu.

  3. #3
    Ngày gia nhập
    09 2013
    Nơi ở
    Hồ Chí Minh
    Bài viết
    33

    Lúc học tớ cũng thấy thắc mắc như cậu, nhưng khi đọc sách thấy có mấy cái thuật toán chưa được chứng mình, hoặc nếu chứng minh được thì cũng cực kỳ phức tạp nên cũng không quan tâm lắm. Cái này học ở mức độ biết và hiểu thuật toán là được rồi cậu, chứng minh cái này ở dạng "hàm lâm" mất rồi (để mấy ông GS, TS)

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

    Hàn lâm là 10 thì mấy cái này 1 thôi. Tới lớp giải thuật thì ai cũng phải chứng minh mấy cái này hết mà.

  5. #5
    Ngày gia nhập
    02 2014
    Nơi ở
    TP.HCM
    Bài viết
    1,006

    Với những anh em không được học qua chuyên ngành thì đúng là "hàn lâm" rồi, thấy mấy ký hiệu như trên là em xin chạy mất dép nói chi tới chuyện chứng minh ( em chả .. em chả ... dám đâu )

  6. #6
    Ngày gia nhập
    01 2013
    Bài viết
    1,479

    Mặc định Chứng minh độ phức tạp của các thuật toán trong C

    Trích dẫn Nguyên bản được gửi bởi MHoang Xem bài viết
    Với những anh em không được học qua chuyên ngành thì đúng là "hàn lâm" rồi, thấy mấy ký hiệu như trên là em xin chạy mất dép nói chi tới chuyện chứng minh ( em chả .. em chả ... dám đâu )
    Dù sao thì profiler với benchmark soft là tiếng nói sau cùng

  7. #7
    Ngày gia nhập
    05 2014
    Bài viết
    3

    Vâng em cảm ơn mọi người ạ. Chắc em cũng phải chạy mất dép thôi Khó quá

Tags của đề tài này

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