java - 第一个列表已排序，另一个未排序，这是合并两个列表的更好方法

Question

我有一个已排序的 ArrayList A 和一个未排序的 ArrayList B，现在我想合并 A 中 B 的项目，以便 A 保持排序。

现在我只能想到两种方法。

First one is to sort Arraylist B and then have two index positions one for Arraylist A and other for Araylist B, then we will move index one by one to insert B list's item in A.

让我们假设 Arraylist A 的大小为 n，Arraylist B 的大小为m。

复杂度的顺序为 O(m Log(m))(用于对 ArrayList B 进行排序)+ O(n + m)。

Second Approach is just have an index on ArrayListaylist B and then use Binary search to place item from Arraylist B to A.

复杂度顺序为 O(Log(n) * m)。

现在谁能告诉我我应该选择哪种方法，如果您能想到比这两种方法更好的其他方法，请提及。

Answer 1

这取决于n和m的相对大小。

当 n > m*log(m) 第一个算法的运行时间复杂度为 O(m*Log(m) + max(n,m)) 将由 n 上的线性项支配(注意在这种情况下 max(n,m)=n 为 n > m*log(m)).在这种情况下，复杂度 O(log(n) * m) 的第二种算法会更好。

确切的实际截止点将取决于每个算法特定实现的常数因子，但原则上，随着 n 相对于 m 变大，第二种算法会变得更好>，最终成为更好的选择。换句话说，对于 m 的每个可能值，n 都存在一个足够大的值，因此第二种算法更好。

编辑:以上部分错误

我回答时假设两种算法的复杂度都给定，但现在我不确定第二种算法的复杂度是否正确。您建议使用二进制搜索将未排序列表中的每个数字插入到已排序列表中，但您将如何执行此操作？如果您有链表，则无法进行二进制搜索。如果你有一个数组，你需要在每次插入时替换数组的一部分，这是每次插入的线性开销。我不确定是否有办法使用更复杂的数据结构来实现这一点，但您不能使用链表或数组来实现。

澄清一下，如果您有两个具有这些时间复杂度的算法，那么我的原始答案成立，但您的第二个算法没有我们假设的 O(m log(n)) 复杂度。