获得2个有序列表并集的最有效算法

Question

我需要找到2个降序有序列表(list1和list2)的并集,其中union将是两个列表中的每个元素,没有重复.假设列表元素是整数.我使用大O表示法来确定解决此问题的最有效算法.我知道第一个的大O符号,但我不知道第二个的大O符号.有人能告诉我第二个算法的大O符号,以便我可以决定实现哪种算法？如果有人知道比其中一个更好的算法,你能帮我理解吗？提前致谢.

Here are my two algorithms. . .

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Algorithm #1: O(N * log base2 N)

Starting at the first element of list1, 
while(list1 is not at the end of the list) {
    if(the current element in list1 is not in list2)    // Binary Search -> O(log base2 N)
        add the current element in list1 to list2
    go to the next element in list1 }

list2 is now the union of the 2 lists

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Algorithm #2: O(?)

Starting at the first elements of each list,
LOOP_START:
    compare the current elements of the lists
    whichever element is greater, put into a 3rd list called list3
    go to the next element in the list whose element was just inserted into list3
    branch to LOOP_START until either list1 or list2 are at the end of their respective list
insert the remaining elements from either list1 or list2 into list3 (the union)

list3 now contains the union of list1 and list2

Answer 1

第二个是O(n + m),而第一个是O(n log(m)+ m).因此,第二个明显更好.

Answer 2

这是我对情况的评估

• 你的第一个算法在n log n时间运行:你正在对第一个列表中的每个元素进行二进制搜索,对吗？
• 你的第二个算法并不完全:如果两个列表中的元素相等,你就不说该怎么做.但是,给定处理相等元素的正确逻辑,您的第二个算法就像合并排序的合并部分:它将以线性时间(即N)运行.从某种意义上说,它是最优的,你不能做得更好:你不能合并两个有序列表而不至少查看两个列表中的每个元素.