【文件属性】:
文件名称:TopK优化思路
文件大小:302KB
文件格式:DOCX
更新时间:2021-10-10 13:46:58
算法
TopK,不难;其思路优化过程,不简单:
• 全局排序,O(n*lg(n))
• 局部排序,只排序TopK个数,O(n*k)
• 堆,TopK个数也不排序了,O(n*lg(k))
• 分治法,每个分支“都要”递归,例如:快速排序,O(n*lg(n))
• 减治法,“只要”递归一个分支,例如:二分查找O(lg(n)),随机选择O(n)
• TopK的另一个解法:随机选择+partition