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ố 13 kết quả

Đề tài: Chứng minh độ phức tạp thuật toán bất kỳ!

  1. #1
    Ngày gia nhập
    11 2007
    Nơi ở
    Trái đất
    Bài viết
    7

    Mặc định Chứng minh độ phức tạp thuật toán bất kỳ!

    Ai giúp tôi cái này với. Vì từ trước tới nay cứ nhìn vào thuật toán là biết độ phức tạp chứ có bao giờ chứng minh đâu, nay thầy lại bắt phải chứng minh. Các bạn biết thì giúp tôi với nha.
    Không có việc gì khó
    Chỉ sợ tiền không nhiều
    Đào núi và lấp biển
    Không làm được thì đi thuê.

  2. #2
    Ngày gia nhập
    07 2007
    Nơi ở
    Sơn La
    Bài viết
    133

    Mình đang học về CTDL & GT. Nhưng chưa học về đánh giá thuật toán, độ phức tạp...Nhưng theo mình thì xét đến khả năng xấu nhất, tốt nhất để tỉm ra độ phức tạp.
    Bạn bảo là nhìn vào thuật toán là biết độ phức tạp, vậy sao lại không chứng minh được nhỉ?
    Có gì chỉ thêm cho mình với, có lẽ cũng sắp học đến rồi.
    Ngoài ra mình có thể cài thêm một chương trình kiểm tra thời gian chạy của mỗi thuật toán rồi so sánh , liệu có xét được tính tổng quát không?
    Cái này mình nghĩ vậy chứ chưa thực hiện nó.
    Trao đổi kiến thức sẽ giúp ta tiếp cận nhanh với kiến thức.

  3. #3
    Ngày gia nhập
    11 2007
    Nơi ở
    Trái đất
    Bài viết
    7

    Òi thì thưởng là thấy lặp 1 vòng for thì bảo nó có độ phức tạp n. 2 vong ***g nhau thì n^2. Tuy nhiên một số thuật toán không thể nhìn là biết được độ phức tạp. Thứ 2 nữa là, biết thì biết thế, chứ chứng mình làm sao nó như thế mới là quan trọng.
    Không có việc gì khó
    Chỉ sợ tiền không nhiều
    Đào núi và lấp biển
    Không làm được thì đi thuê.

  4. #4
    Ngày gia nhập
    07 2006
    Nơi ở
    Hanoi, Vietnam
    Bài viết
    2,750

    Cứ nhìn vào thuật toán biết ngay là độ phức tạp bao nhiêu, chứng tỏ cậu phải là cao thủ về bói toán.

    Dr có ý này: Khỏi cần phải chứng minh làm gì, vì chứng minh cũng là để tìm ra độ phức tạp của giải thuật. Chi bằng Thầy giáo cứ thoải mái đưa ra giải thuật, cậu cho biết luôn độ phức tạp. Chắc là thầy cho điểm liền và còn mời làm trợ lý ruột nữa đó.

    Muốn học được giải thuật và chứng minh giải thuật tốt trước hết bạn phải học tốt môn "Cấu trúc dữ liệu". Còn không thì cũng chỉ là "Biết mà không biết" mà thôi.

    Tham khảo thêm bài viết đầu tiên của đề tài sau đây sẽ rất có ích cho bài viết bạn đưa ra đó.
    http://forums.congdongcviet.com/showthread.php?t=3617
    Email: admin[@]congdongcviet.com | CC to: info[@]congdongcviet.com
    Phone: 0972 89 7667 (Office: 04 6329 2380)
    Yahoo & Skype: dreaminess_world (Vui lòng chỉ rõ mục đích ngay khi liên hệ, cảm ơn!)

    Một người nào đó coi thường ý thức kỷ luật cũng có nghĩa là người đó đã coi thường tương lai số phận của chính bản thân người đó. Những người coi thường ý thức kỷ luật sẽ không bao giờ có được sự thành công trong sự nghiệp!

  5. #5
    Ngày gia nhập
    07 2007
    Nơi ở
    Sơn La
    Bài viết
    133

    Nếu bạn nói vậy, theo mình thì nó liên quan tới phương pháp đếm trong toán rời rạc rồi.
    Đặc biệt liên quan tới dirichlet, hoặc những bài toán tổ hợp.Có nghĩa ở đây chúng ta sẽ đếm số bước chạy của chương trình.
    Theo bạn thì sao?
    Trao đổi kiến thức sẽ giúp ta tiếp cận nhanh với kiến thức.

  6. #6
    Ngày gia nhập
    11 2007
    Nơi ở
    Trái đất
    Bài viết
    7

    Mặc định Chứng minh độ phức tạp thuật toán bất kỳ!

    Vẫn biết vậy bác ạ, cám ơn bác đã cho đọc một bài về sự khiêm tốn, nhưng biết mà không biết thì coi như không biết, mình muốn hiểu cơ bản của nó, chính vì thế mà mình mới hỏi.
    Không có việc gì khó
    Chỉ sợ tiền không nhiều
    Đào núi và lấp biển
    Không làm được thì đi thuê.

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

    Vấn đề này mình có đọc qua vài sách, nó không đơn giản và cần đến kiến thức toán rời rạc và tích phân ứng dụng. Nhưng những giải thuật chúng ta học sẽ không đến nổi quá phức tạp đâu, bạn cứ yên tâm.
    Mình sẽ lấy 1 ví dụ cho bạn hiểu rõ hơn :
    BT : Hãy tìm giá trị trả về của đoạn mã lệnh sau đây, sử dụng Big O.
    Code:
    function mystery ( n )
    1:r = 0;
    2:for ( i = 1; i <= n-1; i++)
    3:      for ( j = i+1; j <= n; j++)
    4:          for ( k = 1; k <= j; k++ )
    5:                    r = r + 1;
    6:         return r;
    Mình sẽ kí hiệu tổng Reiman Sum ( chữ Z ngược là S nhé vì mình nghĩ diễn đàn không ghi ra được kí hiệu toán học, bạn thông cảm )
    CM :
    Vòng lập for ở dòng thứ 4-5 có cùng 1 tác dụng như ta thực hiện phép gán : r = r + j;. Vì thế vòng lập từ dòng 3-5 có tác dụng sau đây :
    Code:
     for ( j = i + 1; j <= n; j++ )
                   r = r + j,
    mà điều này sẽ tương đương với :
    Code:
     r = r + S(j=i+1;n) j [/php]
    <=> S(j=i+1;n) j = S (j=1;n)j - S(j=1;i)j = n(n+1)/2 - i(i+1)/2
    Vì thế vòng lập từ dòng 2-5 có tác dụng như sau :
    Code:
    for ( i = 1; i <= n-1; i++ )
           r = r + n(n+1)/2 - i(i+1)/2 
    <=> r = r + S(i=1;n-1)(n(n+1)/2 - i(i+1)/2)
    <=> S(i=1;n-1)(n(n+1)/2 - i(i+1)/2 )
    <=> [(n-1)n(n+1)]/2 - 1/2 S(i=1;n-1)i^2 - 1/2S(i=1;n-1)i
    <=> (n-1)n(n+1)/2 - n(n-1)(2n-1)/12 - n(n-1)/4
    <=> n(n^2 -1)/3
    Vì vậy hàm trên sẽ trả về n(n^2 -1)/3. Và vòng for lập bắt đầu từ dòng thứ 2 thực hiên cho O(n) lần lặp. Và vòng for lặp ở dòng 3 cũng thực hiện cho O(n) lần lặp. Và tượng tự cho vòng for bắt đầu từ dòng 4 cũng O(n) lần lặp. Ta suy ra từ dòng 1-5 có O(1) lần. Vì vậy hàm trên sẽ trả về thời gian là O(n^3). Cái này do kí tự O có thể bỏ qua hằng. Nếu bạn học qua chắc mình nghĩ bạn cũng biết ký tự này rồi phải không. Mình có vài tài liệu về dùng toán để giải giải thuật, khi nào có dịp mình sẽ post lên cho bạn tham khảo thêm nhé.Mình thấy thực ra thuật toán có bản chất là toán học. Hi vọng chúng ta sẽ có dịp thảo luận, bản thân mình cũng rất thích thuật toán ~~ Thân ! Hope it help !
    Đã được chỉnh sửa lần cuối bởi rox_rook : 14-11-2007 lúc 02:47 PM.

  8. #8
    Ngày gia nhập
    11 2007
    Nơi ở
    Trái đất
    Bài viết
    7

    Okei rất cám ơn nếu bạn cho mình tham khảo với.
    Không có việc gì khó
    Chỉ sợ tiền không nhiều
    Đào núi và lấp biển
    Không làm được thì đi thuê.

  9. #9
    Ngày gia nhập
    10 2006
    Nơi ở
    Hà Nội
    Bài viết
    146

    có lẽ như thế này, mình có vài ý kiến:

    Vấn đề đánh giá thuật toán là vấn đề rất khó, không hề đơn giản. không chỉ phải có kiến thức sâu sắc mà phải thực sự tinh tế mới được.

    mình có một số tài liệu rất hữu ích cho công việc này, do dung lượng lớn ko up đc, nếu bạn nào có nhu cầu thì pm mình theo địa chỉ: nthanhson.pro@gmail.com thì mình sẽ send cho.

    mình đảm bảo, đọc xong các tài liệu này, bạn thực sự đã có rất nhiều kiến thức bổ ích, và bạn cảm thấy sẽ yêu thích công việc đánh giá thuật táon cũng nên.
    ^^
    fun!

  10. #10
    Ngày gia nhập
    09 2007
    Bài viết
    724

    Trích dẫn Nguyên bản được gửi bởi PoPoPoPo Xem bài viết
    .

    mình có một số tài liệu rất hữu ích cho công việc này, do dung lượng lớn ko up đc, nếu bạn nào có nhu cầu thì pm mình theo địa chỉ: nthanhson.pro@gmail.com thì mình sẽ send cho.

    mình đảm bảo, đọc xong các tài liệu này, bạn thực sự đã có rất nhiều kiến thức bổ ích, và bạn cảm thấy sẽ yêu thích công việc đánh giá thuật táon cũng nên.
    ^^
    fun!
    mình nghĩ là bạn nên up lên trang một trang web ví như:http://www.box.net và đưa ra một cái link để mọi người ai cần thì vào đó down về. để đỡ mất công hơn cho mọi người.
    Cám ơn bạn rất nhiều.

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

  1. Algorithm Tìm hiểu thuật toán gom cụm sử dụng liên kết đầy đủ và cài đặt chương trình minh họa.
    Gửi bởi bang651990 trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 5
    Bài viết cuối: 18-06-2017, 08:24 PM
  2. Chương trình chứng minh định lý bằng thuật toán Vương Hạo(Havard)
    Gửi bởi zkday2686 trong diễn đàn Dự án & Source code VC++
    Trả lời: 21
    Bài viết cuối: 20-10-2016, 11:32 PM
  3. Thuật toán số thông minh với C#
    Gửi bởi tesulakata trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 2
    Bài viết cuối: 13-08-2010, 07:30 AM
  4. Minh họa bằng đồ thị thuật toán sắp xếp trên C
    Gửi bởi Mr.Kjng trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 13
    Bài viết cuối: 12-08-2009, 10:24 AM
  5. [Khác]Chứng minh độ phức tạp của Thuật toán, vấn đề không dễ!
    Gửi bởi PoPoPoPo trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 3
    Bài viết cuối: 09-10-2007, 10:49 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