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

Đề tài: Thuật toán sắp xếp dãy số A có độ phức tạp O(n) thì dùng thuật toán nào?

  1. #1
    Ngày gia nhập
    09 2010
    Bài viết
    9

    Post Thuật toán sắp xếp dãy số A có độ phức tạp O(n) thì dùng thuật toán nào?

    Đề bài : Cho một mảng A gồm n số nguyên có giá trị trong khoảng [0,n^2-1]. Viết một thuật toán sắp xếp A có độ phức tạp O(n).
    Các pro giúp mình nhé ! Cảm ơn nhiều lắm
    Đã được chỉnh sửa lần cuối bởi maythywinter : 13-10-2011 lúc 09:30 PM.

  2. #2
    Ngày gia nhập
    12 2010
    Nơi ở
    Hanoi, Vietnam, Vietnam
    Bài viết
    687

    Trích dẫn Nguyên bản được gửi bởi maythywinter Xem bài viết
    Đề bài : Cho một mảng A gồm n số nguyên có giá trị trong khoảng [0,n^2-1]. Viết một thuật toán sắp xếp A có độ phức tạp O(n).
    Các pro giúp mình nhé ! Cảm ơn nhiều lắm
    sử dụng thuật toán sắp xếp đếm phân phối độ phức tạp là 0(max( giá trị lớn nhất của mảng , n))
    hoặc là bucketsort độ phức tạp trong trường hợp tốt nhất là 0(n +k);
    cậu có thể lên google search để biết thêm !

  3. #3
    Ngày gia nhập
    09 2010
    Bài viết
    9

    OK! Mình cũng đang định sử dụng thuật toán sắp xếp đếm phân phối. Bắt tay vào làm thôi, có gì không biết các bạn hỗ trợ mình nhé !

  4. #4
    Ngày gia nhập
    11 2010
    Bài viết
    589

    Trích dẫn Nguyên bản được gửi bởi maythywinter Xem bài viết
    OK! Mình cũng đang định sử dụng thuật toán sắp xếp đếm phân phối. Bắt tay vào làm thôi, có gì không biết các bạn hỗ trợ mình nhé !
    theo như đề bài của bạn thì giá trị mỗi phần tử có thể lên đến n^2-1, tức là nếu dùng thuật toán đếm phân phối thì độ phức tạp là O(n^2) chứ không phải là O(n) nữa.

  5. #5
    Ngày gia nhập
    09 2010
    Bài viết
    9

    Trích dẫn Nguyên bản được gửi bởi boss14420 Xem bài viết
    theo như đề bài của bạn thì giá trị mỗi phần tử có thể lên đến n^2-1, tức là nếu dùng thuật toán đếm phân phối thì độ phức tạp là O(n^2) chứ không phải là O(n) nữa.
    Vậy thì phải dùng thuật toán nào ?

  6. #6
    Ngày gia nhập
    10 2011
    Bài viết
    554

    Mặc định Thuật toán sắp xếp dãy số A có độ phức tạp O(n) thì dùng thuật toán nào?

    Theo ngu kiến của mình là chả có cái xắp xếp nào mà độ phức tạp O(n) cả . Chí ít nó phải là nlogn.
    Trường hợp thuận lợi thì ko bàn đến. Bởi xác suất gặp trường hợp này rất thấp và nó ko phải là trường hợp tổng quát.

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

  1. Bài toán cái ba lô dùng kỹ thuật nhánh cận
    Gửi bởi thaimun trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 23
    Bài viết cuối: 25-11-2012, 02:18 AM
  2. 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
  3. 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
  4. Thuật toán trộn 2 mảng thành 1 mảng tăng đàn ko dùng thuật toán sắp xếp
    Gửi bởi caphetim trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 6
    Bài viết cuối: 21-03-2011, 06:40 PM
  5. Dùng IDE nào để lập trình thuần C++ với API?
    Gửi bởi mysuncl trong diễn đàn Thắc mắc lập trình Visual C++
    Trả lời: 10
    Bài viết cuối: 28-08-2009, 04:44 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