thuật toán quick sort

[favouritekid]

bạn nào biết cách tìm độ phức tạp của thuật toán quick sort ko...bày mình với...phương pháp để tìm độ phức tạp của các thuật toán khác lun...thanks các bạn nhìu
code:
PROCEDURE Quicksort(i,j:integer);
VAR
Pivot : KeyType;
PivotIndex, k : integer;
BEGIN
PivotIndex := FindPivot(i,j);
IF PivotIndex <> 0 THEN BEGIN
Pivot := a[PivotIndex].key;
k := Partition(i,j,Pivot);
QuickSort(i,k-1);
QuickSort(k,j);
END;
END;

trên lớp thầy mình bảo thuật toán trên có độ phức tạp là:O(nlogn) mà mình cách biết cách tính nó như thế nào...hic..

[quynhlan]

bạn nào biết cách tìm độ phức tạp của thuật toán quick sort ko...bày mình với...phương pháp để tìm độ phức tạp của các thuật toán khác lun...thanks các bạn nhìu

PROCEDURE Quicksort(i,j:integer);
VAR
  Pivot : KeyType;
  PivotIndex, k : integer;
BEGIN
  PivotIndex := FindPivot(i,j);
  IF PivotIndex <> 0 THEN 
  BEGIN
    Pivot := a[PivotIndex].key;
    k := Partition(i,j,Pivot);
    QuickSort(i,k-1);
    QuickSort(k,j);
  END;
END;

trên lớp thầy mình bảo thuật toán trên có độ phức tạp là:O(nlogn) mà mình cách biết cách tính nó như thế nào...hic..

Để dễ tưởng tượng ta lấy một giá trị cụ thể n=16. Vậy cho lần gọi QuickSort(i,j) đầu tiên:

i=1 và j=16.

FindPivot() có thời gian thực hiện là hằng.

Partition(i,j) quét hết chiều dài mảng từ i đến j, thời gian thực hiện là 16. Ta sẽ thể hiện thời gian này bằng đoạn thẳng độ dài 16 đơn vị:

----------------

Ta lại giả sử pivot nằm ở chính giữa mảng. Vậy tiếp theo đó sẽ là lời gọi đệ quy Quicksort(1,8), trên mảng độ dài 8:

----------------
--------

Rồi gọi đệ qui Quicksort(1,4), Quicksort(1,2). Tại đây, lần đầu tiên, thuật toán không tiến sâu nữa mà lùi trở ra:

----------------
--------
----
--

Vẽ thêm bước Quicksort(3,4) nữa:

----------------
--------
----
----

Vẽ thêm bước Quicksort(5,8) nữa:

----------------
--------
--------
----

Vẽ thêm bước Quicksort(5,6) nữa:

----------------
--------
--------
------

Vẽ thêm bước Quicksort(7,8) nữa:

----------------
--------
--------
--------

Và cứ thế tiếp diễn. Sau bước cuối cùng thì ta được thời gian tổng cộng là:

----------------
----------------
----------------
----------------

bằng n * log2(n).

Chú ý rằng độ phức tạp n*log(n) này được tính ra trong giả thiết pivot luôn được tìm ra ở vị trí chính giữa mảng và nhờ vậy cặp lệnh QuickSort(i,k-1); QuickSort(k,j); tiến hành trên cặp mảng con cùng độ dài.

Suy luận tương tự như thế, giả sử pivot luôn được tìm ra ở vị trí cuối mảng ta được thời gian thực hiện

----------------
---------------
--------------
-------------
------------
-----------
----------
---------
--------
-------
------
-----
----
---
--

bằng n(n+1)/2 -1. Độ phức tạp là n^2.

[VuongChieuQuan]

Chả hiểu đồng chí này viết cái gì. Nhưng kết quả thì kết luận một câu sai bét.
Độ phức tạp của thuật toán quicksort là O(nlg(n)). Nhỏ hơn nhiều so với n^2.
Còn để tính độ phức tạp cho nó mình biết một cách sử dụng thống kê + ngẫu nhiên. Cái này bạn có thể tham khảo trong một số sách chuyên ngành. Còn các phưong pháp khác thì mình chưa thấy.

[quynhlan]

Chả hiểu đồng chí này viết cái gì. Nhưng kết quả thì kết luận một câu sai bét.

Không hiểu thì đừng bình luận vội.

Độ phức tạp của thuật toán quicksort là O(nlg(n)). Nhỏ hơn nhiều so với n^2.

QL đã nêu 2 đáp số: n*log(n) và n^2, ứng với 2 trường hợp riêng. Bạn vui lòng đọc kỹ lại đi.

Còn để tính độ phức tạp cho nó mình biết một cách sử dụng thống kê + ngẫu nhiên. Cái này bạn có thể tham khảo trong một số sách chuyên ngành.

Đúng thế. Để chính xác phải chứng minh được 2 điều

+ n*log(n) là độ phức tạp bình quân (đúng cho đa số trường hợp).
+ n^2 là độ phức tạp cho trường hợp xấu nhất.

Chứng minh những điều này đòi hỏi kiến thức thống kê tổ hợp, một lĩnh vực chuyên ngành. Vài dòng trên forum thì không làm được.

[VuongChieuQuan]

Ù ! Xin lỗi quynhlan ! Đọc nhanh quá không để ý kĩ ! Sorry sorry !!!!!

[nguyenlinh85]

Chào các bạn!
MÌnh cũng đang đi tìm tài liệu chứng minh chi tiết độ phức tạp của thuật toán quicksort. MÌnh chỉ cần trong trường hợp xấu nhất O(n^2). Ban nao biết xin chi dùm với! Cảm ơn rất nhiều.

[cunbong24]

Hãy đến thư viện thành phố, trường hoặc thư viện quốc gia mượn quyển:"Data structure & Algorithm Analysis In C++", tác giả Mark Allen Weiss, Tom 2, Trang 265 đến trang 279 sẽ thấy phân tích để tính độ phức tạp của Quick Sort Algorithm một cách tổng quát nhất.