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

Đề tài: [Khác]Chứng minh độ phức tạp của Thuật toán, vấn đề không dễ!

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

    Smile [Khác]Chứng minh độ phức tạp của Thuật toán, vấn đề không dễ!

    Có lẽ bản thân mỗi ai học về toán học nói chung và về IT nói riêng cũng phải nghiền ngẫm các môn "Giải thuật_Thuật toán". Có lẽ tính nhân văn trong nó, hay cái đích của môn này là tính khả dụng và độ phức tạp của thuật toán.

    Về độ khả dụng thì ta không bàn.
    Ta sẽ bàn về độ phức tạp của thuật toán, hay nói cách khác là thời gian tính toán hay số phép tính.

    Có lẽ sau khi học về thuật toán gì các bạn cũng thấy phần đánh giá thuật toán với độ phức tập tính toán là O(n^2), O(2^n)...

    Thường một số thuật toán rất dễ đánh giá, nhưng một số tỏ ra rất khó. Nhiều lúc chúng ta nghe người ta nói, rồi công nhận luôn, ít khi để tâm nó có đúng không.

    Mình có câu hỏi:

    Hãy chứng minh độ phức tạp tính toán của Thuật toán sắp xếp Merge Sort là O(n*logn).

    Nếu bạn là dân IT, hãy suy nghĩ về nó thử nha!
    Đã được chỉnh sửa lần cuối bởi iamvtn : 26-09-2007 lúc 08:38 PM.

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

    Nếu bạn có ý tưởng cho một thuật toán mới mà bạn cho là tối ưu hơn 1 thuật toán nào đó đã có trước đó thì bạn phải chứng mình điều đó, có nghĩa là:
    • Bạn phải chứng minh tính đúng của thuật toán, tức là thuật toán của bạn phải cho ra kết quả đúng (hay cho kết quả chấp nhận được).
    • Bạn phải chứng minh là độ phức tạp tính toán của bạn là nhỏ hơn các thuật toán đã có


    vì vậy mình mong muốn các bạn nên có cho mình một ý thức riêng trong vấn đề học và nghiên cứu thuật toán.

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

    để giải bài toán này các bạn phải nắm đc thuật toán của merge sort là ji?
    từ đó để suy ra.
    Thực ra cũng không quá khó, chỉ cần các bạn chịu khó suy nghĩ 1 tẹo thôi
    Cố gắng lên nhé.

  4. #4
    Ngày gia nhập
    06 2007
    Nơi ở
    một nơi xa xăm...
    Bài viết
    127

    Tiếp tục đi popo.Ngày trước mình cũng học về đánh giá độ phức tạp của thuật toán nhưng lại dạy qua qua nên mình cũng không hiểu lắm.Nếu có thể popo cho 1 tut về cái này đi.Từ cơ bản đên khó hơn.Vì mình thấy cái này cũng rất quan trọng...

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. Chứng minh độ phức tạp thuật toán bất kỳ!
    Gửi bởi KimDaiHiep trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 12
    Bài viết cuối: 16-06-2012, 11:31 AM
  4. 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
  5. 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

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