数据结构与算法最优解解释

Question

我目前正在做ds&一个udemy课程，因为我正在为即将到来的秋季大量招聘做准备。我偶然发现了一个问题，它的大意是：

给定列表数组，计算第一个列表数组中存在的第二个列表数组中缺少的整数

课程中给出了两种解决方案，一种被认为是蛮力解，另一种被认为是最优的。

以下是解决办法：

def finderBasic(list1,list2):

    list1.sort()
    list2.sort()
    
    for i in range(len(list1)):
        if list1[i] != list2[i]:
            return list1[i]

def finderOptimal(list1,list2):

    d = collections.defaultdict(int)

    for num in list2:
        d[num] = 1
    
    for num in list1:
        if d[num] == 0:
            return num
        else:
            d[num] -= 1

本课程解释说，finderOptimal是解决问题的最优方法，因为它以O(n)或线性方式解决问题。谁能再给我解释一下为什么。我只是觉得finderBasic要简单得多，只经历了一个循环。任何帮助都将不胜感激，谢谢！

Answer 1

如果只是通过循环，那么第一个解决方案会更好。--就像你说的，遍历一个for循环(整体)需要O(n)时间，不管是一次、两次还是c次(只要c足够小)。

然而，这里的繁重操作是排序，因为它需要cca n*log(n)时间，这比O(n)要大。这意味着，即使在第二个解决方案中运行了两次for循环，它仍然比排序一次要好得多。

请注意，访问字典键大约需要O(1)时间，所以循环的时间仍然是O(n)时间。

参见：https://wiki.python.org/moin/TimeComplexity

对于读者来说，基本的解决方案可能更好，因为它非常简单和直接，但是它更复杂。

Answer 2

免责声明:我不熟悉python。

在第一个例子中，有两个循环是没有考虑的。每个sort()调用至少有两个嵌套循环来实现排序。最重要的是，通常情况下，在执行排序时O(n log(n))是最好的性能。

第二种情况避免了所有的排序，只使用一张“扑克牌”来标记存在的内容。此外，它使用字典，它是一个哈希表。我相信您已经了解到哈希表提供恒定的时间-- O(1) -操作。

更简单并不总是意味着最有效。相反，效率往往难以理解。