将两个各有 N 个元素的有序表归并成一个有序表,其最少的比较次数是( )
【解析】 归并排序基本思想 :归并排序是多次将两个或两个以上的有序表合并成一个新的有序
表。最简单的归并是直接将两个有序的子表合并成一個有序的表归并排序最好情况下的复杂度
将两个各有 N 个元素的有序表归并成一个有序表,其最多的比较次数是( )
【解析】最多的比較次数是当两个有序表的数据刚好是插空顺序的时候,比如:第一个序列是1,3,5第二个序列是2,4,6,把第二个序列插入到第一个序列中先把第②个序列中的第一个元素2和第一个序列依次比较,需要比较2次(和13比较),第二个元素4需要比较2次(和3,5比较因为4比2大,2之前的元素都鈈用比较了)第三个元素6需要比较1次(只和5比较),所以最多需要比较5次即2n-1次。
发布了68 篇原创文章 · 获赞 40 · 访问量 4万+