时间戳

首页 > 解决方案 > 这三种解决方案的时间复杂度是多少？

python - 这三种解决方案的时间复杂度是多少？

问题描述

我有这三个 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])

标签： pythontime-complexity

解决方案

为什么最后一个函数的速度是第一个函数的两倍？

大 O 表示法的分析时间复杂度看起来对所有人都是一样的，但受常数影响。例如，这O(n)实际上意味着在比较时间复杂度O(c*n)时c被惯例忽略。

您的每个函数都有不同的c. 尤其是

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

因此，函数/语句的假设固定开销测量c(for) > c(sum) > c(len)在哪里。c(f)f

你可以通过反汇编每个函数来检查我的假设。

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

这些函数的时间复杂度是多少？

请注意，虽然所有函数都具有相同的大 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都有一个传递，反之亦然，所以总时间在. 有关详细信息，请参阅Python 的 TimeComplexity wiki。JSO(n*m)

推荐阅读