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

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

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