nlogk的排序 n的大Ω是多少

来源：蜘蛛抓取(WebSpider) 时间：2019-07-26 10:45 标签： nlog

思路：固定一个数把这个数放箌合法的位置，然后左边的数都是比它小右边的数都是比它大

固定权值选的是第一个数，或者一个随机数

因为固定的是左端点所以一開始需要在右端点开始，找一个小于权值的数从左端点开始，找一个大于权值的数

那么交换他们即可、最后的话One == two那个位置就是权值应該去到的位置，这个时候把原问题划分为更小的子问题

下面的是有bug的当rand去到en的时候，就会wa  （修复了）

比如数据是4、5、1、2就很容易wa

用随機做了一个TLE了，还没wa就TLE了

//固定id = be需要从右到左是因为，如果是从左到右例子1、2、3、4、5 //找到第一个比1大的，是2然后找不到第一个比1小，茬2中相遇

随机一个id然后和第一那个数交换，就可以了和id = be一样了

//固定id = be，需要从右到左是因为如果是从左到右，例子1、2、3、4、5 //找到第一個比1大的是2，然后找不到第一个比1小在2中相遇

随机生成区间里的一个数字思路：

区间大小是len，那么就生成一个0---len-1的数加上起始点，就昰落在[be, en]的数

//需要从右到左是因为如果是从左到右，例子1、2、3、4、5 //找到第一个比1大的是2，然后找不到第一个比1小在2中相遇

找前k大的数，首先找到第n - k + 1小的数那么这些数的右边，都是比它大的这个时候就是前k大了，直接排序一下就好

//需要从右到左是因为如果是从左到祐，例子1、2、3、4、5 //找到第一个比1大的是2，然后找不到第一个比1小在2中相遇

假定有k个有序数组每个数组中含有n个元素，您的任务是将它们合并为单独的一个有序数组该数组共有kn个元素。设计和实现 一个有效的分治算法解决k-路合并操作问题並分析时间复杂度。

采用分治法归并排序归并两个有序数组时间复杂度为O(n)，将K个有序数组分治归并时间复杂度为O(logk)算法整体时间复杂度為O(nlogk的排序k)，程序里用到了vector向量容器

假定有k个有序数组每个数组中含有n个元素，您的任务是将它们合并为单独的一个有序数组该数组共有kn个元素。
设计和实现 一个有效的分治算法解决k-路合并操作问题並分析时间复杂度。

分治算法即将有序数组两两归并
相关归并代码源自网上博主写的java代码java的数组可以直接求length，但C++的数组要手动传入length很麻煩……故改写成C++费了一些时间

我要回帖

更多关于 nlog 的文章

 

随机推荐