Độ phức tạp của QuickSort

[Dao_Trong_Hieu (Hoàng Vlog)]

Em không hiểu cách người ta đánh giá thời gian trung bình của QuickSort là như thế nào, tại sạo lại chia ra thành 2 O(n/9) và O(9n/10). Và giải như thế nào nó như thế nào
Nguồn: https://www.geeksforgeeks.org/quick-sort/

[tntxtnt]

nếu em đọc được tiếng anh thì tìm cuốn Intro to Algorithm 3rd ed. của CLRS mà đọc ấy.

trong đó họ lấy ví dụ trường hợp pivot chia mảng hiện tại thành 2 khúc 9/10 và 1/10, đpt vẫn là O(n \log{n}). Sau đó họ nói thêm nếu chia thành 2 khúc 99/100 và 1/100 thì đpt vẫn là O(n \log{n}). Hay nói cách khác nếu pivot chia mảng thành 2 khúc có tỉ lệ ko đổi x% và (100-x)% thì đpt vẫn là O(n \log{n}).

trích từ CLRS trang 176 :V

quicksort chỉ có đpt O(n^2) khi pivot nó chia mảng thành 1 khúc k phần tử và n-k phần tử với k là hằng số thì phải :V
Đương nhiên k/n = y% thì cũng có thể chém gió là O(n \log{n}), nhưng k nhỏ quá thì y% cũng nhỏ quá thì hằng số của O(n \log{n}) đó quá lớn nên cũng coi như gần bằng O(n^2) :V Ví dụ n=1000, tổng các phép so sánh là 100n \log{n} thì mặc dù nó là O(n \log{n}) đấy nhưng 100 nó cũng gần bằng 1000 nên cũng tiệm cận O(n^2) rồi :V
Còn k lớn thì y% lớn nên O(n^2) có hằng số rất nhỏ nên gần gần bằng O(n \log{n}) :V Ví dụ 0.05 n^2 với n = 1000 ~ 50k, so với ví dụ 2n \log{n} là ~20k , 50k với 20k thì cũng xêm xêm :V

[Dao_Trong_Hieu (Hoàng Vlog)]

Cái O(n^2) là trường hợp tồi nhất khi chọn phần tử chốt là lớn nhất hoặc nhỏ nhất.
Khi đấy ta có thể suy ra phương trình đệ quy rồi sử dụng định lý thợ là ra O(n^2)

[rogp10]

Gọi X_n là số lần so sánh hai phần tử của Quicksort với dãy có độ dài n. Mỗi phần tử được so sánh đúng một lần với phần tử chốt, tức là n phép so sánh. Với E(X_2) = 1 mảng có thể được chia làm đôi theo n-1 cách, ở đây ta giả sử là đồng khả năng. Áp dụng công thức kỳ vọng toàn phần:

n\geq 3: E(X_n) = \frac{2}{n-1}\cdot\sum_{i=2}^{n-1}E(X_i) + n\ (*)

(*) sẽ fit với y = C_1\cdot n\log(n + C_2) nên ta áp dụng định nghĩa big-O: \exists\ c, E(X_n) \leq c\cdot n\ln n
Áp dụng định nghĩa tích phân:

\begin{aligned} E(X_k) &\leq \frac{2c}{k}\int_{1}^{k} (x\ln x)\ dx + k\\ &= \frac{2c}{k}(\frac{k^2}{2}\ln{k}\ - \frac{k^2}{4} + \frac{1}{4}) + k\\ &< c\cdot k\ln k - \frac{c}{2}\cdot k + \frac{1}{2} \cdot k + k\\ &= c\cdot k\ln k - \frac{c-3}{2}\cdot k \end{aligned}

Chọn c = 3 để triệt tiêu bậc nhất ta có đpcm.