合并法排序的数据结构的一道问题
来源:学生作业帮 编辑:作业帮 分类:数学作业 时间:2024/09/03 00:52:52
合并法排序的数据结构的一道问题
有n个整数,他们分别存在m个子数列(sub-array)中,(n>1,m>1,n>>m) 设计一个排序算法,伪代码就可以,使得n个整数升序排列,并且最重要的是,要让算法比O(n log 2 n)(以二为底)更快,并且分析一下他的big-O.
有n个整数,他们分别存在m个子数列(sub-array)中,(n>1,m>1,n>>m) 设计一个排序算法,伪代码就可以,使得n个整数升序排列,并且最重要的是,要让算法比O(n log 2 n)(以二为底)更快,并且分析一下他的big-O.
不基于比较的可以么 如果是不基于比较的突破O(n)分分钟的事情.
如果不行的话 就两两合并嘛. n>>m 应该是可以比nlogn快的
再问: 两两合并的话big-O是怎样?
再答: 要看情况 合并一个长为l1 和一个长为 l2 的数组 的 复杂度大概是 o(l1+l2) 呃 你的这种情况让我想到了一道经典的题目合并石子.....差不多的道理
如果不行的话 就两两合并嘛. n>>m 应该是可以比nlogn快的
再问: 两两合并的话big-O是怎样?
再答: 要看情况 合并一个长为l1 和一个长为 l2 的数组 的 复杂度大概是 o(l1+l2) 呃 你的这种情况让我想到了一道经典的题目合并石子.....差不多的道理