合并两个大小为 n 和 m 的排序数组的最差运行时间情况

Question

我正在做一个问题，我对在长度为 n 和 m 的两个数组上使用合并排序的最坏情况感到有点困惑。问题已经表明它们已排序，并且我假设它们分别大小相等。

但是我很难决定运行 tome 的最坏情况是 n*m 还是 max(n, m)。可能有不止一个答案，但我只是在努力思考这两个答案是否符合我的理解。

我翻了一下笔记，由于两者已经排序，所以我想到的大部分问题似乎只是关于是否是 n + m 还是其他什么。

Answer 1

答案是m+n。 为了更好地理解，举个例子：

m =[1,2,3,4]

和

n=[5,6,7]

。在这种情况下，

len(m) > len(n)

的大小或相反的大小并不重要，因为要合并，您必须完全迭代

m

，然后迭代

n

。