【在 g***s 的大作中提到】 : Even if it is not sorted, the finding median of all (k*n) item only needs : O(k*n)
g*s
14 楼
1. put all number into one array, size = k*n O(k*n) 2. find the median of the array O(k*n) I think LZ is asking for a better solution since the above method doesn't care if it is sorted or not in the k arrays. 【 在 lolhaha (haha) 的大作中提到: 】
g*s
15 楼
yes, for k=2, O(lgN) is surely much better.
doesn't
【在 g***s 的大作中提到】 : 1. put all number into one array, size = k*n O(k*n) : 2. find the median of the array O(k*n) : I think LZ is asking for a better solution since the above method doesn't : care if it is sorted or not in the k arrays. : 【 在 lolhaha (haha) 的大作中提到: 】
n*p
16 楼
what if the memory can only hold two arrays rather than all the arrays.
【在 g***s 的大作中提到】 : 1. put all number into one array, size = k*n O(k*n) : 2. find the median of the array O(k*n) : I think LZ is asking for a better solution since the above method doesn't : care if it is sorted or not in the k arrays. : 【 在 lolhaha (haha) 的大作中提到: 】
CLRS -> Chapter 9: Medians and Order Statistics -> Selection in worst-case linear time
g*s
20 楼
here we are discussing a solution better than O(kn) 【 在 anson627 (anson) 的大作中提到: 】 case
a*7
21 楼
the book already assumed each sorting in O(1) time, when the sub-array is small enough. I don't think we can do better in worst case. On average case, maybe.