7

我需要找到 2 个降序列表（list1 和 list2）的联合，其中联合将是两个列表中没有重复的每个元素。假设列表元素是整数。我正在使用大 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
4

8 回答 8

8

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

于 2013-03-18T06:22:57.147 回答
8

这是我对情况的评估

  • 您的第一个算法在n log n时间内运行：您正在对第一个列表中的每个元素进行二进制搜索，对吗？
  • 您的第二个算法并不完全完整：如果两个列表中的元素相等，您不会说该怎么做。但是，考虑到处理相等元素的正确逻辑，您的第二个算法就像合并排序的合并部分：它将在线性时间内运行（即N）。这是最佳的，从某种意义上说，你不能做得比这更好：你不能在不查看两个列表中的每个元素至少一次的情况下合并两个有序列表。
于 2013-03-18T06:23:43.440 回答
1

使用以下算法，您可以在 O(n+m) 中合并两个列表。

[对不起，为了简单起见，我使用了python，但算法在每种语言中都是相同的]

请注意，该算法还维护在结果列表中排序的项目。

def merge(list1, list2):
    result = []
    i1 = 0;
    i2 = 0;
    #iterate over the two lists
    while i1 < len(list1) and i2 < len(list2):
        #if the current items are equal, add just one and go to the next two items
        if list1[i1] == list2[i2]:
            result.append(list1[i1])
            i1 += 1
            i2 += 1
        #if the item of list1 is greater than the item of list2, add it and go to next item of list1
        elif list1[i1] > list2[i2]:
            result.append(list1[i1])
            i1 += 1
        #if the item of list2 is greater than the item of list1, add it and go to next item of list2
        else:
            result.append(list2[i2])
            i2 += 1
    #Add the remaining items of list1
    while i1 < len(list1):
        result.append(list1[i1])
        i1 += 1
    #Add the remaining items of list2
    while i2 < len(list2):
        result.append(list2[i2])
        i2 += 1
    return result

print merge([10,8,5,1],[12,11,7,5,2])

输出：

[12, 11, 10, 8, 7, 5, 2, 1]
于 2013-12-10T22:12:40.120 回答
0

复杂性分析：

假设列表 1 的长度为N，列表 2 的长度为M。

算法 1：
冒着听起来令人难以置信的风险，我会接受，根据我的说法，这种算法的复杂性是 是N * M而不是NlogM。

对于列表 1 中的每个元素(O(N))，我们在列表 2 中搜索它(O(logM)。该算法的复杂性“似乎” O(NlogM)。

但是，我们也在列表 2 中插入元素。这个新元素应该插入适当的位置，以便列表 2 保持排序以进行进一步的二进制搜索操作。如果我们使用数组作为数据结构，那么插入需要O(M)时间。

因此，复杂度的顺序是O(N*M)算法的原样。

可以进行修改，其中将新元素插入到列表 2 的末尾（然后列表不再有序），并且我们从 index0 to M-1而不是从new size-1. 在这种情况下，复杂性将是因为我们将在长度列表中O(N*logM)执行二进制搜索。NM

为了使列表再次排序，我们必须合并两个有序部分（0 到 M-1 和 M 到 newSize-1）。这可以在 O(N+M) 时间内完成（数组长度为 N+M 的合并排序中的一次合并操作）。因此该算法的净时间复杂度应为 

O(NlogM + N + M)

空间复杂度O(max(N,M))不考虑原始列表空间，仅考虑列表 2 中所需的额外空间。

算法 2：
在每次迭代中，我们至少向前移动 1 个指针。两个指针移动的总距离为N + M。因此，最坏情况下的时间复杂度顺序O(N+M)优于第一种算法。

但是，这种情况下所需的空间复杂度更大（O(N+M)）。

于 2013-12-04T11:34:43.013 回答
0

这是另一种方法：遍历两个列表，并将所有值插入到一个集合中。这将删除所有重复项，结果将是两个列表的并集。两个重要的注意事项：你会失去数字的顺序。此外，它需要额外的空间。

时间复杂度：O(n + m)

空间复杂度：O(n + m)

如果您需要维护结果集的顺序，请使用一些自定义版本的 LinkedHashMap。

于 2013-12-07T09:14:17.483 回答
0

实际上，如果输入列表未排序，算法 2 不应该工作。要对数组进行排序，它的顺序是 O(m*lg(m)+ n*lg(n))

您可以在第一个列表上构建一个哈希表，然后对于第二个列表中的每个项目，检查该项目是否存在于哈希表中。这在 O(m+n) 中有效。

于 2013-12-10T20:54:55.777 回答
0

有几点需要指定：

  • 输入列表是否包含重复项？
  • 必须订购结果吗？

我假设，使用std::list，您可以廉价地插入头部或尾部。

假设列表 1 有 N 个元素，而列表 2 有 M 个元素。

算法 1

它遍历列表 1 的每个项目，在列表 2 中搜索它。

假设可能存在重复并且必须对结果进行排序，则搜索的最坏情况是列表 1 中的元素不存在于列表 2 中，因此至少是：

  • O(N × M)。

要将 List 1 的项插入到正确的位置，您需要再次迭代 List 2 直到插入点。更糟糕的情况是 List 1 中的每个项目都更小（如果从头搜索 List 2）或更大（如果从尾搜索 List 2）。由于列表 1 的先前项已插入到列表 2 中，因此第一项将进行 M 次迭代，第二项将进行 M + 1 次，第三项将进行 M + 2 次等，最后一项将进行 M + N - 1 次迭代项目，平均每个项目 M + (N - 1) / 2。

就像是：

  • N × (M + (N - 1) / 2)

对于大 O 表示法，常数因子无关紧要，所以：

  • N × (M + (N - 1))

对于大 O 表示法，非变量加法无关紧要，所以：

  • O(N × (M + N))

添加到原始 O(N × M)：

  • O(N × M) + O(N × (M + N))
  • O(N × M) + O(N × M + N 2 )

第二个方程只是为了使常数因子消除明显，例如2×（N×M），因此：

  • O(N × (M + N))
  • O(N 2 + N × M)

这两个是等价的，你最喜欢哪个。

可能的优化：

  • 如果不需要对结果进行排序，则插入可以是 O(1)，因此更糟糕的情况是：

    • O(N × M)

  • 不要只用相等来测试List 2中的每一个List 1项，而是用eg大于来测试每一项，这样当List 1的item大于List 2的item时，你就可以停止在List 2中的搜索；这不会减少最坏的情况，但会减少平均情况

  • 保持 List 2 迭代器指向 List 1 的项被发现大于 List 2 的项的位置，以进行排序插入 O(1)；在插入时确保保留一个从插入项开始的迭代器，因为虽然 List 1 是有序的，但它可能包含重复项；有了这两个，更糟糕的情况变成：

    • O(N × M)

  • 对于下一次迭代，使用我们保留的迭代器在列表 2 的其余部分中搜索列表 1 的项目；这减少了最坏的情况，因为如果您到达列表 2 的末尾，您将只是从列表 1 中“删除”重复项；有了这三个，更糟糕的情况变成：

    • O(N + M)

至此，该算法与算法 2 之间的唯一区别是列表 2 被更改为包含结果，而不是创建一个新列表。

算法 2

这就是归并排序的归并。

您将遍历 List 1 的每个元素和 List 2 的每个元素一次，并且插入总是在列表的头部或尾部进行，因此最坏的情况是：

  • O(N + M)

如果有重复，它们就会被丢弃。结果比没有更容易订购。

最后的笔记

如果没有重复，则可以在两种情况下优化插入。例如，使用双向链表，我们可以轻松地检查 List 1 中的最后一个元素是否大于 List 2 中的第一个元素，反之亦然，然后简单地连接列表。

这可以进一步推广到 List 1 和 List 2 的任何尾部。例如，在算法 1 中，如果在 List 2 中找不到 List 1 的项目，我们可以将 List 2 和 List 1 的尾部连接起来。在算法 2 中，这是在最后一步完成的。

更糟糕的情况是，当列表 1 的项目和列表 2 的项目交错时，并没有减少，但平均情况再次减少，并且在许多情况下，减少了在 Real Life™ 中产生重大影响的一个重要因素。

我忽略了：

  • 分配时间
  • 算法中更糟糕的空间差异
  • 二进制搜索，因为您提到了列表，而不是数组或树

我希望我没有犯任何明显的错误。

于 2013-12-10T23:42:48.583 回答
0

在我之前的一个项目中，我已经实现了基于 typescript(js) 的 2 个对象数组的联合操作的实现。数据太大，下划线或 lodash 等默认库函数并不乐观。经过一番脑筋急转弯，我想出了以下基于二进制搜索的算法。希望它可以帮助某人进行性能调整。

就复杂性而言，该算法是基于二进制搜索的，最终将是 O(log(N))。

基本上，代码需要两个无序对象数组和一个键名进行比较，并且：1）对数组进行排序 2）遍历第一个数组的每个元素并将其删除到第二个数组中 3）将生成的第二个数组连接到第一个数组中。

    private sortArrays = (arr1: Array<Object>, arr2: Array<Object>, propertyName: string): void => {
        function comparer(a, b) {
            if (a[propertyName] < b[propertyName])
                return -1;
            if (a[propertyName] > b[propertyName])
                return 1;
            return 0;
        }

        arr1.sort(comparer);
        arr2.sort(comparer);
    }

    private difference = (arr1: Array<Object>, arr2: Array<Object>, propertyName: string): Array<Object> => {

        this.sortArrays(arr1, arr2, propertyName);

        var self = this;

        for (var i = 0; i < arr1.length; i++) {
            var obj = {
                loc: 0
            };
            if (this.OptimisedBinarySearch(arr2, arr2.length, obj, arr1[i], propertyName))
                arr2.splice(obj.loc, 1);
        }

        return arr2;
    }

    private OptimisedBinarySearch = (arr, size, obj, val, propertyName): boolean => {
        var first, mid, last;
        var count;

        first = 0;
        last = size - 1;
        count = 0;

        if (!arr.length)
            return false;
        while (arr[first][propertyName] <= val[propertyName] && val[propertyName] <= arr[last][propertyName]) {
            mid = first + Math.floor((last - first) / 2);

            if (val[propertyName] == arr[mid][propertyName]) {
                obj.loc = mid;
                return true;
            }
            else if (val[propertyName] < arr[mid][propertyName])
                last = mid - 1;
            else
                first = mid + 1;
        }
        return false;
    }

    private UnionAll = (arr1, arr2, propertyName): Array<Object> => {
        return arr1.concat(this.difference(arr1, arr2, propertyName));
    } 

    //example
    var YourFirstArray = [{x:1},{x:2},{x:3}]
    var YourSecondArray= [{x:0},{x:1},{x:2},{x:3},{x:4},{x:5}]
    var keyName = "x";
    this.UnionAll(YourFirstArray, YourSecondArray, keyName)
于 2017-01-02T15:12:58.627 回答