為什么，合并兩個長度分別為m和n的有序表，最壞情況下需要比較m n-1次?數(shù)據(jù)結(jié)構(gòu)的一道題？假設有序表是按升序排列的。對于長度相同的兩個有序表（例如，長度為n），最差的是2N-1，即相互交叉的情況，在

為什么，合并兩個長度分別為m和n的有序表，最壞情況下需要比較m n-1次?數(shù)據(jù)結(jié)構(gòu)的一道題？

假設有序表是按升序排列的。對于長度相同的兩個有序表（例如，長度為n），最差的是2N-1，即相互交叉的情況，在第二層解釋。如果長度不相等，則長度分別為m和N，最差的為mn-1，但不一定相交。例如，長度為M的有序表的第一個M-1元素小于長度為N的有序表的第一個元素，并且第M個元素大于長度為N的有序表的第N個元素（即所有元素），因此比較的次數(shù)是M-1 N。事實上，最壞的情況是所有元素都已比較，并且每次表中放入一個元素。也就是說，在排列完mn-1元素之后，我們比較mn-1次，但是最后一個元素顯然不需要再比較，所以我們直接把它放到表中，所以總共是M-1n次。