瑞士手表排名 ZT (转载)# PhotoGear - 摄影器材
f*m
1 楼
大家都讨论过了,这里想再确定一下:
给定m个sorted linked list or array,平绝长度为n。则:
(1)divide conquer:
T(mn)=2T(mn/2)+O(mn) =>T(mn)=mnlog(mn)
(2) minheap:
m(构造Heap)+(mn-m)logm=〉mnlogm
(3)从一个list拿出头元素与其他list的头元素比较:
mn*m。
由此可见(1)和(3)不一定哪个好,决定于m和n的值。m或n很大时(1)比(3)好。
请指教。
给定m个sorted linked list or array,平绝长度为n。则:
(1)divide conquer:
T(mn)=2T(mn/2)+O(mn) =>T(mn)=mnlog(mn)
(2) minheap:
m(构造Heap)+(mn-m)logm=〉mnlogm
(3)从一个list拿出头元素与其他list的头元素比较:
mn*m。
由此可见(1)和(3)不一定哪个好,决定于m和n的值。m或n很大时(1)比(3)好。
请指教。