算法的内省
Abstract
工程实战中使用的算法往往都不是完整的某个算法, 他们会”智能”地根据实际情况选择适合的解法。比如说快速排速中会在数量少的时候使用插入排序, 并且将完全的递归实现改为半递归的实现(递归到一定深度后使用别的算法)。又比如在做二分查找边界条件的处理比较麻烦, 那就在快到达边界条件时使用朴素算法保证正确。
- 考虑最坏的情况也能有比较好的性能
- 动态检测
top k
top k的内省改造。一般思路: 排序。但其实我们并不需要对全部都排序。e.g.
- 快排: 如果我们只要top一半, 那一遍后显然另一半就可以不用了