小编cpr*_*y89的帖子

我需要找到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 …