老题目一问# JobHunting - 待字闺中
a*d
1 楼
array of N elements, find M smallest elements. N >> M
我说选pivot 再partition,
expected complexity is: n + n/2 + n/4 ... = 2n.
问我还可以再提高吗?都O(n)了还怎末improve, 除非再constant上做文章。
没想出来。
同胞说可以 "n" 做出来。。。
我说选pivot 再partition,
expected complexity is: n + n/2 + n/4 ... = 2n.
问我还可以再提高吗?都O(n)了还怎末improve, 除非再constant上做文章。
没想出来。
同胞说可以 "n" 做出来。。。