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

Đề tài: Giúp mình hiểu cách đánh giá độ phức tạp của giải thuật vs

  1. #1
    Ngày gia nhập
    09 2011
    Nơi ở
    Hanoi, Vietnam, Vietnam
    Bài viết
    3

    Mặc định Giúp mình hiểu cách đánh giá độ phức tạp của giải thuật vs

    Xác định độ phức tạp của hàm T(n) = 10*(n^3) + (log"2" của (n^10+1))


    Mình biết 10*(n^3)= O(n^3) rồi nhưng vế còn lại thì ko hiểu? :(

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

    log"a" (b)^n = n*log"a" (b)

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

  3. #3
    Ngày gia nhập
    09 2011
    Nơi ở
    Hanoi, Vietnam, Vietnam
    Bài viết
    3

    nhưng mà đây là (n^10+1) cơ mà ?
    với lại nó<= đa thức nào với n>=n0 nào đó?

  4. #4
    Ngày gia nhập
    09 2011
    Nơi ở
    Hanoi, Vietnam, Vietnam
    Bài viết
    3

    chính xác là n^10+1<= đa thức nào đó với n>= n0 nào đó ;

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

    n^10+1 ~ n^10
    Thuật toán duyệt + cận hay sao mà phức tạp thế

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

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

    Mặc định Giúp mình hiểu cách đánh giá độ phức tạp của giải thuật vs

    T(n)= 10* (n^3) + log2(n^10+1) = 10*(n^3)=n^3 . O(n^3)

    Vấn đề là tính độ phức tạp log2(n^10+1) . Mới vào nhìn cái log là thấy nó có mùi vị của PHẦN BÉ rồi
    Ta thấy log2(n^10+1) < log2(n^10+n^10) = log2(2n^10) = 1 + 10log2(n) = O(log2(n)) .
    Vậy log2(n^10+1) = O(log2(n)) .
    Cái này thì vô cùng bé so với n^3 . Cho cả lý luận của toán học hay quy tắc Cộng của lĩnh vực thuật toán thì nó đều chỉ phụ thuộc vào n^3. Cái log bé quá, ko chơi .


    Vì 1 lý thuyết nói như sau : g(n) > f(n) thì O(g(n)) cũng là độ phức tạp của f(n). Trong 1 số trường hợp ko thể tìm trực tiếp độ phức tạp của 1 cái f(n) nào đó, người ta thường tìm 1 cái g(n) > f(n) mà càng gần sát với f(n) càng tốt và nhận O(g(n)) là độ phức tạp của f(n)
    Đã được chỉnh sửa lần cuối bởi clchicken : 21-10-2011 lúc 07:47 PM.

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

  1. Giải thích giúp Giải thuật Euclid (tìm ƯSCLN)
    Gửi bởi duoirong trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 15
    Bài viết cuối: 15-04-2015, 12:06 PM
  2. Giải thuật shaker sort. Giúp mình giải thuật với?
    Gửi bởi nguyenhai trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 6
    Bài viết cuối: 29-01-2015, 10:53 PM
  3. Bài tập C Cần giải giúp 3 câu trong đề thi kĩ thuật lập trình C và Cấu trúc dữ liệu và giải thuật
    Gửi bởi nguyenthi0602 trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 2
    Bài viết cuối: 24-09-2012, 08:42 PM
  4. lưu đồ giải thuật bài mã đi tuần thuật toán quay lui vét cạn. Giúp mình với?
    Gửi bởi katemat000 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 1
    Bài viết cuối: 05-01-2010, 10:53 PM
  5. Tài liệu về giải thuật mã hóa. Mã hóa file theo giải thuật DES. Ai có giúp mình?
    Gửi bởi daolong83 trong diễn đàn Công cụ, ebooks C#, ASP.NET, và Windows Mobile
    Trả lời: 6
    Bài viết cuối: 17-07-2009, 11:28 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