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

Đề tài: Kết luận độ phức tạp của thuật toán như thế nào?

  1. #1
    Ngày gia nhập
    04 2009
    Bài viết
    17

    Mặc định Kết luận độ phức tạp của thuật toán như thế nào?

    Mình có đoạn lý thuyết thê này:

    + Trong trường hợp xấu nhất(dãy có thứ tự ngược lại), ta tính được:
    HVxấu = SSxấu = (n-1) + (n-2) + (n-3) + ….. + 2 + 1 =n(n-1)/2
    + Trong trường hợp tốt nhất( dãy đã được sắp):
    HVtôt =0
    SStôt =n-1
    Tóm lại, độ phức tạp của thuật toán:
    Ttôt(n) = O(n).
    Txấu(n) = O(n^2).

    Các bạn giải thích giúp mình đoạn tóm lại đó.Mình không hiểu nó như thế nào cả.Vì sao ở trên trường hợp xấu là n(n-1)/2 mà ở dưới kết luận là O(n^2)
    Mình rất gà về vấn đề này, càng chi tiết càng tốt nha các bạn.
    Cảm ơn tất cả.

  2. #2
    Ngày gia nhập
    12 2006
    Bài viết
    7

    n(n-1)/2 = n^2/2 -n/2
    Khi n rất lớn thì giá trị của biểu thức trên sẽ quyết định bởi giá trị của n^2. Do đó người ta viết n(n-1)/2 là O(n^2), đọc là: lớn đáng kể của n^2.
    Chú ý là nếu n^2/100 thì người ta cũng chỉ chú ý đến số mũ, và vẫn viết O(n^2).

    Có thể lấy thêm 1 số ví dụ để bạn hiểu rõ hơn:

    (n-6)(n-8)(n+1)/8 -n == O(n^3)
    nlgn+n+sqrt(n) == O(nlgn)

  3. #3
    Ngày gia nhập
    04 2009
    Bài viết
    17

    Bạn nói vậy là mình hiểu rùi. Chân thành cảm ơn bạn Peach@

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

  1. Giải thuật Thảo luận giải thuật xác xuất. 27 con lô
    Gửi bởi binhpt2612 trong diễn đàn Thắc mắc CTDL & Giải thuật
    Trả lời: 0
    Bài viết cuối: 21-06-2013, 01:45 PM
  2. Giải thuật xóa các phần tử trong mảng [Thảo luận]
    Gửi bởi trungkien45 trong diễn đàn Thắc mắc CTDL & Giải thuật
    Trả lời: 16
    Bài viết cuối: 04-03-2013, 03:08 PM
  3. Phân đoạn ảnh theo thuật toán Kruskal, mong mọi người thảo luận thêm?
    Gửi bởi IBU1603 trong diễn đàn Thắc mắc CTDL & Giải thuật
    Trả lời: 0
    Bài viết cuối: 14-04-2012, 04:35 PM
  4. Algorithm Thảo luận thuật toán xử lý ma trận trong C#
    Gửi bởi the_link trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 6
    Bài viết cuối: 31-08-2011, 09:59 AM
  5. Chuẩn hóa căn thức - thảo luận thuật toán
    Gửi bởi mp121209 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: 11-09-2010, 10:37 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