python - 这三个解的时间复杂度是多少？

Question

我有一个 Leetcode 问题的这三个解决方案，并不太了解这里时间复杂度的差异。为什么最后一个函数的速度是第一个函数的两倍？

68 毫秒

def numJewelsInStones(J, S):
    count=0
    for s in S:
        if s in J:
            count += 1
    return count

40毫秒

def numJewelsInStones(J, S):
    return sum(s in J for s in S)

32毫秒

def numJewelsInStones(J, S):
    return len([x for x in S if x in J])

Answer 1

Why is the last function twice as fast as the first one?

根据大 O 符号的分析时间复杂度看起来对所有的人都一样，但是受制于常量。那就是例如O(n) 实际上意味着 O(c*n)，但是在比较时间复杂度时，c 按照约定被忽略。

您的每个函数都有不同的c。特别是

• 循环通常比生成器慢
生成器的
• sum 可能在 C 代码中执行(求和部分，添加数字)
• len 是对数组的简单属性“单操作”查找，可以在常数时间内完成，而 sum 需要 n添加操作。

因此 c(for) > c(sum) > c(len) 其中 c(f) 是函数/语句的假设固定开销度量 f.

您可以通过 disassembling 检查我的假设每个函数。

除此之外，您的测量值可能会受到系统中运行的其他进程引起的变化的影响。要从您的分析中消除这些影响，请取每个函数至少 1000 次调用的平均执行时间(您可能会发现 c 可能小于此变化，但我并不期望如此)。

what is the time complexity of these functions?

请注意，虽然所有函数都具有相同的大 O 时间复杂度，但后者会根据您用于 J、S 的数据类型而有所不同。如果 J, S 是类型:

• dict，你的函数的复杂度将在O(n)
• set，你的函数的复杂度将在O(n)
• list，您的函数的复杂度将在 O(n*m) 中，其中 n,m 是J, S 变量，分别。请注意，如果 n ~ m 这将有效地变成 O(n^2)。换句话说，不要使用 list。

为什么数据类型很重要？因为 Python 的 in 运算符实际上只是为特定类型实现的成员资格测试的代理。具体来说，dict 和 set 成员测试在 O(1) 中工作，时间为常数，而 list 在 O(n) 时间内工作。因为在 list 的情况下，对于 S 的每个成员，J 的每个成员都有一个传递，反之亦然，总时间在O(n*m)。参见 Python's TimeComplexity wiki了解详情。