Python

Question

下面这个函数的复杂度是多少？？

def find_set(string, chars):
    schars = set(chars)
    for i, c in enumerate(string):
        if c in schars:
            return i
    return -1 

print(find_set("Happy birthday", "py"))

在这种情况下，返回 1，因为 H 在 CHEERIO 的索引 1 处。

是否可以进一步优化此功能？

Answer 1

您的（最坏情况）时间复杂度为 O(len(string) * len(set))。是的，你可以做得更好（至少从算法的角度来看）。

def find_set(string, chars):
    schars = set(chars)
    return next((i for i, c in enumerate(string) if c in schars), -1)

这应该在 O(len(chars) + len(string)) 内执行（最坏情况）。当然，说到"optimization"，通常你应该忘记你自以为知道的和简介。仅仅因为我的算法复杂度更高并不意味着它会在你的真实世界数据上表现得更好。

Python - 查找索引位置函数

Python - Finding Index Location Function

string

character