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

Đề tài: xin hỏi về đánh giá độ phức tạp thuật toán

  1. #1
    Ngày gia nhập
    07 2007
    Bài viết
    2

    Red face xin hỏi về đánh giá độ phức tạp thuật toán

    Để đánh giá độ phức tạp của thuật toán nguòi ta dùng kí pháp O,tôi vẫn chưa hiểu về cái này,các bạn giải thích dum tôi đi

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

    Để đánh giá độ phức tạp của thuật toán thường thì dùng BigO nhưng để hiểu rõ thì phải có 1 tí kiến thức về toán rời rạc :
    - Nếu |f(x)| <= C|g(x)| khi và chỉ khi tồn tại x > k nào đó thì f(x) có bigO(g(x)).
    Nếu đúng thì đáng lý phải làm cả 2 chiều cho cả bigOmega thì mới thực sự chính xác -> cận trên và dưới, nhưng trong thuật toán người ta thường chỉ dùng cận trên : bigO.
    Ví dụ :
    cho hàm số f(x) = x^2 + 2x + 1(1). Chứng minh nó là bigO(x^2).
    Ta có : x^2 + 2x + 1 < x^2 + 2x^2 + x^2
    <-> (1) < 4x^2 với mọi x > 1 ( chỗ k này có thể chọn bất kì để thỏa mãn bài toán là đủ, ở đây tui chọn k = 0 thì dấu = xảy ra vậy thôi).
    Nhớ là >= nghĩa là > hoặc =, chứ không phải > và bằng.
    Vậy rõ ràng là C = 4, k = 1 -> hàm đó là bigO(x^2)
    Hay nói cách khác nó có độ phức tạp là x^2.
    Cái đó là toán học h xét vào tin học xem :
    C++ Code:
    1.  for(int x = 0; x < n; ++x)
    2.     {
    3.         for(int y = 0; y < n; ++y)
    4.         {
    5.             //tính toán gì đó
    6.         }
    7.     }
    Cứ mỗi 1 x thì có ứng với 0->n sự tính toán. Dùng kí hiệu Sima Tổng thì dễ dàng thấy nó là có độ phức tạp là x^2. Nhưng do tui type không được, nên bạn tự CM đi, nhớ là tổng 1 + 2 + 3... n = n(n + 1)/2
    Cứ làm cho nhiều vào thì sẽ có cảm giác với độ phức tạp, nhưng nói chung cũng tùy bài. Thường thì các vòng lặp sẽ có độ phức tạp là bigO(n).

  3. #3
    Ngày gia nhập
    10 2006
    Nơi ở
    Rừng Amazon
    Bài viết
    101

    Cái đó là đánh giá chung chung thôi, còn độ phức tạp còn phải hiểu theo cả độ phức tạp về thời gian và không gian nhớ nữa.

    Không gian nhớ ngày càng rẻ, nên độ phức tạp thời gian được nhắc đến dưới dạng 'số lượng phép toán bit cần phải thực hiện'.

    Để tính được nó, cần có thuật toán chi tiết chứ nói nôm na là vòng lặp có O(n) thì cũng đúng một phần.

    Bác rox_rook viết bài này tốt quá. Không vote được nhỉ.

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

  1. Dịch thuật, công ty dịch thuật, dịch vụ dịch thuật chuyên nghiệp
    Gửi bởi vecvn trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 4
    Bài viết cuối: 18-11-2012, 10:44 PM
  2. Dịch vụ kế toán: Báo cáo thuế, dịch vụ tư vấn thuế, báo cáo thuế tncn vnnp
    Gửi bởi ecomvnnp01 trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 1
    Bài viết cuối: 16-02-2012, 11:07 AM
  3. Bài tập C++ Viết chương trình nhập số lượng hàng hóa, giá cả, thuế, xuất ra tổng giá, thuế, tổng cộng
    Gửi bởi seit 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: 04-03-2011, 09:04 AM
  4. Hướng dẫn kê khai thuế thu nhập cá nhân, thuế doanh nghiệp 0903034381
    Gửi bởi thngxanhcty trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 0
    Bài viết cuối: 19-05-2010, 02:33 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