python - 如何计算此代码的时间复杂度？

问题描述

我正在经历 HackerRank 问题，我有这个问题：

给定嵌入在约翰每块岩石中的矿物清单，显示他收藏的宝石类型的数量。例如，矿物成分字符串数组是 ['abc', 'abc', 'bc]。矿物 b 和 c 出现在每个复合物中，因此有 2 颗宝石。

我有一个解决方案，但我想问一下时间复杂度：

def gemstones(arr):
    counter = 0
    char_set = set(''.join(arr))
    for ch in char_set:
        if all(ch in word for word in arr):
            counter+=1
    return counter

我认为时间复杂度是 O(n+m) 是否正确，其中 n 是 char_set 中的元素数，m 是 arr 中的元素数？

标签： pythontime-complexity

正确的复杂度是 O(N)：

def gemstones(arr) :
    return len(set(arr))

这将返回正确数量的宝石，忽略重复项。

你不必为此计算矿物质。

下面是人力资源问题的链接，针对该问题的解决方案是：

def gemstones(arr):
    x = set(arr[0])
    for a in arr :
        x.intersection_update(set(a))
    return len(x)

python - 如何计算此代码的时间复杂度？

问题描述

解决方案

推荐阅读