首页 > 试题广场 >

最坏情况下，合并两个大小为n的已排序数组所需要的比较次数为(

[填空题]
最坏情况下，合并两个大小为n的已排序数组所需要的比较次数为1
添加回答
推荐
november头像 november
编辑于 2015-02-07 15:08:38 回复(3)
晨不二头像 晨不二
比较一次，添加一个数。最坏情况下，2n个数要比较2n-1次。
编辑于 2016-02-21 16:39:54 回复(1)
coolcyy头像 coolcyy
a1与b1比较取a1，b1与a2比较取b1，一直这样交替比较，an与bn比较取an，最后bn不用比较。所以是2n-1
发表于 2015-08-05 23:33:43 回复(3)
Amour1018头像 Amour1018
最坏情况下，合并两个大小为n的已排序数组所需要的比较次数为  2n-1;
最好情况下，合并两个大小为n的已排序数组所需要的比较次数为 n＋1.
发表于 2015-09-23 09:54:02 回复(2)
飞鱼_6头像 飞鱼_6
两个数组把其中一个数组遍历完就算比较完成。最坏的情况ab两个数组都遍历了n-1 这时候比较了2n-2次。两个数组各剩下一个还要比较一次。所以2n-2+1。 最好的情况 遍历n次所有数据都从a中取 a数组遍历完。比较了n次
发表于 2016-07-31 23:48:43 回复(0)
JerryCheese头像 JerryCheese
最好的情况不是一次吗
发表于 2015-12-18 08:29:05 回复(0)
郑元元头像 郑元元
变一下题目： 最好情况下，合并两个大小为n的已排序数组所需要的比较次数为   n+1  
发表于 2015-08-12 17:08:36 回复(5)
Forrestcloud头像 Forrestcloud
举例子，最坏情况2*n-1
发表于 2017-09-06 15:14:30 回复(0)
七宝Wendy头像 七宝Wendy
2n-1
发表于 2017-08-17 17:51:53 回复(0)
bealikeflower头像 bealikeflower
插空时最坏情况，前n-1个元素往另外一个里面插入比较2次，最后一个比较一次就可以了，所以最坏的话要比较2（n-1）+1=2n-1次

发表于 2017-06-14 22:15:29 回复(0)
霞43头像 霞43
读题要认真，两个大小为n的意思是，每个的大小都为n，一共有2n个数，所以最坏比较n-1次
发表于 2017-06-09 19:06:29 回复(0)
枫桥林葉头像 枫桥林葉
比较一次，添加一个数。最坏情况下，2n个数要比较2n-1次。
发表于 2017-03-15 14:36:35 回复(0)
Pursue_My_Heart头像 Pursue_My_Heart
最好情况下为什么不是一次，比如一个数组最大在最后一个，另一个最小在第一个，两个比较最大的小于最小的，就只需比较一次，这样想哪里不对
发表于 2016-10-30 17:01:02 回复(0)
武汉孙一峰头像 武汉孙一峰
23333 只有我天真的以为，会存在一个递增，一个递减的情况呢0.0，我还一本正经的以为是n*n
1 3 5 7 9
10 9 9 9 9 比25次。
发表于 2016-08-24 13:22:58 回复(0)
-狂战-头像 -狂战-
1，2和4，3合并
4要比较2次才能确定位置，3至少要比较2次才能确定位置
求解？？？
发表于 2016-08-14 14:23:13 回复(0)
魔法鬼事头像 魔法鬼事
第一个数组前面n-1个都比第二个大最后一个比第二个数组都小，这样比较下来是第一个数组的前n-1个数字先进入数组，第二个数组全部进入数组，第一个最后一个进入数组，比较次数是n-1+n
发表于 2016-04-18 08:54:46 回复(0)
tian2016头像 tian2016
不对吧，这两个已排序数组若是一个从小到大，一个从大到小如
1 2 3
6 5 4
按从小到大的次序排，若是直接挨个比较的话，不应该是3×3=9次么，不应该是n^2么？
不挨个比较的话，直接拿1个最大与2中最小比，1次就行。
编辑于 2016-04-12 20:45:28 回复(2)
KYwlzr头像 KYwlzr
2*n-1啊啊啊
发表于 2016-04-10 10:07:56 回复(0)
guoxun1993头像 guoxun1993
2×(n-1)+1
发表于 2016-03-10 10:06:06 回复(0)
cdboy头像 cdboy
简单点
（1） 1 2 3 和4 5 6 归并：比较次数为n=3
（2） 1 3 5和 2 4 6 归并：比较次数为2n-1=2*3-1=5
走一遍这个过程应该就明白了 
编辑于 2016-01-06 15:10:13 回复(2)
提交观点

问题信息

数组 微软 排序
上传者：JC
难度：
20条回答 10975浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号