+ Trả lời chủ đề
Results 1 to 5 of 5

Chủ đề: Tính độ phức tạp đệ quy

  1. #1
    Member
    Gia nhập
    04-2011
    Bài viết
    36
    Cảm ơn
    26
    Được cảm ơn 4 lần trong 3 bài
     

    Tính độ phức tạp đệ quy

    Admin và bạn nào biết giải loại này mong giải giùm và nêu phương pháp giải luôn nhé. Thanks so much.

    Tính độ phức tạp của phương trình đệ quy sau:
    0/ T(n) = T(n-1) + n
    1/ T(n) = T(n-1) + T(n-2) + n
    2/T(n) = 2T(n/2) + logn
    3/T(n) = 3T(n/2) + n
    4/T (n) = 2T (n/2)+ n log n
    5/ T(n) = 4T(n/2) + n2
    6/ T(n) = 4T(n/2) + n3
    7/ T(n) = 4T(n/2) + n
    8/ T (n) = T (n/2) + 2n

    Ai giải dc bài nào thì giải giùm nhé, rất cảm ơn
    Chỉnh sửa sau cùng bởi tamsps; 28-09-2011 lúc 11:59 PM. Lý do: Thêm vài câu nữa.

  2. #2
    Member
    Gia nhập
    04-2011
    Bài viết
    36
    Cảm ơn
    26
    Được cảm ơn 4 lần trong 3 bài
     
    Không ai ai giúp mình dc sao?

  3. #3
    Member
    Gia nhập
    03-2010
    Bài viết
    65
    Cảm ơn
    9
    Được cảm ơn 37 lần trong 27 bài
     
    Nếu mình ko lầm, thì câu 0 & 1, có độ phúc tạp O(n*n)
    Còn từ câu 2 trở đi, độ phúc Tạp O(n log n)

  4. #4
    Member
    Gia nhập
    04-2011
    Bài viết
    36
    Cảm ơn
    26
    Được cảm ơn 4 lần trong 3 bài
     
    Thanks bạn, nhưng có chắc không bạn, vì câu 5 và 6 số mũ của n phía sau là 2 và 3 cơ mà, không biết dùng đinh lý chủ (Master Theorem) có dc không ta.

  5. #5
    Member
    Gia nhập
    03-2010
    Bài viết
    65
    Cảm ơn
    9
    Được cảm ơn 37 lần trong 27 bài
     
    Uhm, theo mình biết thì : tính O() thì ảnh hưởng nhiều nhất là T(n)=T(n gi gi đó) + ....
    Đám động phía sau, có thể xem như hằng số - được tính là 1 phép tính. Vi vậy, khi kết quả cuối cùng, ra là Nlogn + n -> cũng được xem như là Nlogn mà thôi.

    PS : mình nhìn & ước lượng thôi. Muốn chính xác, thì xài định lý chủ (master theorem) để tính, là ok

+ Trả lời chủ đề

Thông tin chủ đề

Users Browsing this Thread

Hiện có 1 người đang xem chủ đề này. (0 thành viên và 1 khách)

     

Những thành viên đã đọc chủ đề này : 4

You do not have permission to view the list of names.

Các quyền đăng bài

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts