2,367
个编辑
更改
跳到导航
跳到搜索
第932行：
第932行： − − Recursive algorithms are often inefficient for small data, due to the overhead of repeated function calls and returns. For this reason efficient implementations of recursive algorithms often start with the recursive algorithm, but then switch to a different algorithm when the input becomes small. An important example is [[merge sort]], which is often implemented by switching to the non-recursive [[insertion sort]] when the data is sufficiently small, as in the [[tiled merge sort]]. Hybrid recursive algorithms can often be further refined, as in [[Timsort]], derived from a hybrid merge sort/insertion sort.
→混合算法
===混合算法===
===混合算法===
由于重复的函数调用和返回，递归算法对于小规模数据往往效率不高。出于这个原因，递归算法的高效实现往往是先实现一个标准递归算法，但当输入变小时，再切换到不同的算法。一个重要的例子是归并排序，当数据足够小的时候，常常通过切换到非递归的插入排序来实现，如'''<font color="#ff8000">平铺合并排序 tiled merge sort</font>'''。混合递归算法往往可以进一步完善，如Timsort中，就是由混合归并排序/插入排序派生出来的。
由于重复的函数调用和返回，递归算法对于小规模数据往往效率不高。出于这个原因，递归算法的高效实现往往是先实现一个标准递归算法，但当输入变小时，再切换到不同的算法。一个重要的例子是归并排序，当数据足够小的时候，常常通过切换到非递归的插入排序来实现，如'''<font color="#ff8000">平铺合并排序 tiled merge sort</font>'''。混合递归算法往往可以进一步完善，如Timsort中，就是由混合归并排序/插入排序派生出来的。