数据结构两个链表合并排序 为什么，合并两个长度分别为m和n的有序表，最坏情况下需要比较m n-1次?数据结构的一道题？

为什么，合并两个长度分别为m和n的有序表，最坏情况下需要比较m n-1次?数据结构的一道题？

假设有序表是按升序排列的。对于长度相同的两个有序表（例如，长度为n），最差的是2N-1，即相互交叉的情况，在第二层解释。如果长度不相等，则长度分别为m和N，最差的为mn-1，但不一定相交。例如，长度为M的有序表的第一个M-1元素小于长度为N的有序表的第一个元素，并且第M个元素大于长度为N的有序表的第N个元素（即所有元素），因此比较的次数是M-1 N。事实上，最坏的情况是所有元素都已比较，并且每次表中放入一个元素。也就是说，在排列完mn-1元素之后，我们比较mn-1次，但是最后一个元素显然不需要再比较，所以我们直接把它放到表中，所以总共是M-1n次。

数据结构两个链表合并排序 两个有序表合并最少比较次数 数据结构顺序表的合并java

版权声明：本文内容由互联网用户自发贡献，本站不承担相关法律责任.如有侵权/违法内容,本站将立刻删除。