2. 计算机
  3. 对n个记录的文件进行二路归并排序，所需要的辅助存储空间为【 】。

对n个记录的文件进行二路归并排序，所需要的辅助存储空间为【 】。

admin2010-05-13  48
问题 对n个记录的文件进行二路归并排序，所需要的辅助存储空间为【  】。
选项
答案O(n)
解析 初始状态没有部分排序的文件中若有n个记录，可以把它看作n个子文件，每个子文件中只包含一个记录，因而是部分排序的。通常先将两个子文件归并，得到n/2个部分排序的较大的于文件，每个子文件中只包含2个记录。再将这些子文件归并，如此反复，直到归并到一个文件中，排序完成。上述每步归并都是将两个子文件全成一个文件，这种做法叫“二路归并排序”。二路归并排序时，需利用一个同待排序数组一样大小的辅助数组，所以其空间复杂度为O(n)。
转载请注明原文地址:https://kaotiyun.com/show/VySZ777K
本试题收录于： 三级数据库技术题库NCRE全国计算机三级分类
0

三级数据库技术

NCRE全国计算机三级

相关试题推荐
随机试题
最新回复(0)