solution

Để so sánh hiệu năng của hai thuật toán A và B một cách phi tham số, người ta đo thời gian chạy trên $n_1$ và $n_2$ lần thử độc lập tương ứng. Sử dụng kiểm định hạng tổng Mann–Whitney (Wilcoxon rank-sum).

Gộp chung $N=n_1+n_2$ quan sát, xếp hạng tăng dần (dùng trung bình hạng cho các giá trị trùng nhau, như mô tả ở bài Spearman). Gọi $R_1$ là tổng hạng của các quan sát thuộc nhóm A.

$U_1 = R_1 - \frac{n_1(n_1+1)}{2}, \qquad U_2 = n_1 n_2 - U_1, \qquad U = \min(U_1,U_2)$

Kỳ vọng và phương sai (có hiệu chỉnh trùng): $\mu_U = \frac{n_1 n_2}{2}, \qquad \sigma_U^2 = \frac{n_1 n_2}{12}\left[(N+1) - \frac{\sum_g (t_g^3-t_g)}{N(N-1)}\right]$ trong đó tổng chạy qua tất cả các nhóm trùng $g$ trong $N$ quan sát gộp, $t_g$ là số phần tử của nhóm trùng đó.

Thống kê chuẩn hoá có hiệu chỉnh liên tục $0.5$: $z = \begin{cases}\dfrac{(U-\mu_U)-0.5}{\sigma_U} & \text{nếu } U > \mu_U\\[4pt] \dfrac{(U-\mu_U)+0.5}{\sigma_U} & \text{nếu } U < \mu_U\\[4pt] 0 & \text{nếu } U=\mu_U\end{cases}$ (quy ước $z=0$ nếu $\sigma_U = 0$). Giá trị $p$ hai phía: $p = 2\left(1-\Phi(|z|)\right)$ với $\Phi$ là hàm phân phối chuẩn tắc (tính qua math.erf).

Kết luận: nếu $p<\alpha$ thì Bac bo H0, ngược lại Khong bac bo H0.

Ví dụ: $n_1=n_2=5$, A = 1 2 3 4 5, B = 6 7 8 9 10 (không trùng nhau, A luôn nhỏ hơn B) $\Rightarrow U_1=0, U_2=25, U=0$.