del*_*del 1 sorting algorithm complexity-theory
想象一下以下场景:我有一个存储在只读存储介质上的10 Mb整数数组.我希望按升序打印出数字.但是,我只有2 Mb的主内存(而且没有硬盘).
一个非常简单的O(n 2)解决方案(不使用可用的主存储器)将重复扫描整个输入数组并逐步输出下一个最小整数.我已经尝试使用谷歌搜索来获得更好的排序算法,但是答案一直引导我使用就地或外部排序算法,由于只读存储约束而无法使用.有更好的解决方案吗？
您可以使用主内存减少扫描次数,使用您给出的大小关系,非常显着.
第一次扫描:使用迄今为止发现的最小数字保持几乎主内存大小的内存存储.虽然商店尚未满,但添加从数组中读取的下一个数字.当商店已满时,与商店中的最大数量进行比较,如果新商品较小,则删除最大数量并添加新商品.扫描完整数组后,按顺序输出找到的数字,记住存储的最大数字以及在此块中发生的频率.
后续扫描:如果扫描的数字等于前一个块中的最大数字,并且其出现次数小于上次扫描的次数,则增加其出现次数,但如果其出现次数较大,则不要将其添加到存储中超过或等于记忆计数将数字添加到商店(如有必要,从商店中删除最大数字).如果扫描的数量大于上一次扫描的最大数量,但小于商店中的最大数量(或商店尚未满),请将其添加到商店(如有必要,请删除最大数量).扫描完成后,按顺序输出存储的数字,并记住到目前为止输出的最大数字,以及总输出的数字(最大数字可能与上次扫描的数字相同,所以你需要知道到目前为止处理的所有块的输出频率.
我不确定商店的最佳数据结构是什么,但我认为堆是一个不错的选择(与最大的比较:O(1),替换:O(日志大小),输出的最终排序:O (size*log size),实际上没有像二叉搜索树那样的内存开销.