Tìm phần tử nhỏ thứ k của ma trận vuông

[Red_Sand (mondlicht1)]

Có nói ở trên rồi đó, complexity không đổi mà, nhưng running time thực tế giảm đáng kể đó chứ :v tất nhiên ko tính với mấy ma trận vài chục triệu trở lên :v

[rogp10]

Bài này vừa đo mem vừa đo time. Chọn trực tiếp là O(n^2) time và O(n^2) mem rồi.

Sử dụng heap thì ngoài O(klogn) còn có O(klogk). O(klogn) dùng n slot mem, còn O(klogk) dùng k slot mem (đều có value, row, col) + n slot int.

O(n) thì quá ngon rồi

Paper dựa trên ma trận nhỏ hơn (đục bỏ hết dòng cột chỉ số chẵn) để suy ra ma trận lớn. Chao Xu cải tiến lại chỉ bỏ cột chỉ số chẵn cho dễ hiểu. Hay T(n) = T(n/2 + O(1)) + O(n), phù hợp với k lớn.