Lei Mao's Log Book
·
CPU TopK算法
💡
原文英文，约2000词，阅读约需7分钟。
📝
内容提要
TopK算法用于在未排序的数组中找到最大或最小的K个元素。常见的两种CPU TopK算法是O(N + KlogN)和O(N)算法。第一种算法使用堆构建和堆提取操作，时间复杂度为O(N + KlogN)。第二种算法使用中位数选择算法和线性扫描或分区算法，时间复杂度为O(N)。两种算法都可以在C++中实现。
🎯
关键要点
- TopK算法用于在未排序的数组中找到最大或最小的K个元素。
- 常见的TopK算法有O(N + KlogN)和O(N)两种。
- O(N + KlogN)算法使用堆构建和堆提取操作。
- O(N)算法使用中位数选择算法和线性扫描或分区算法。
- 堆构建TopK算法的时间复杂度为O(N + KlogN)。
- 提取K个元素需要进行K次堆提取操作，每次操作时间复杂度为O(log N)。
- 中位数选择TopK算法的时间复杂度为O(N)，是线性时间算法。
- 在C++中实现堆构建TopK算法时，可以使用std::make_heap和std::pop_heap。
- 中位数选择TopK算法的实现可以使用std::partition函数进行数组分区。
- 提取的K个元素在堆构建算法中是有序的，但在中位数选择算法中不一定有序。
➡️
