python - 这些排列算法的大 O 符号是什么

Question

通过“Cracking the coding interview”，练习题说

Given 2 strings, write a method to decide if one is a permutation of the other.

笔者的python解决方案如下:

def check_permutation(str1, str2):
    if len(str1) != len(str2):
        return False
    counter = Counter()
    for c in str1:
        counter[c] += 1
    for c in str2:
        if counter[c] == 0:
            return False
        counter[c] -= 1
    return True 

它声称在 O(N) 时间内。

我的解决方案如下:

def perm(str1,str2):
    if(len(str1) != len(str2)):
        return False
    for c in str1:
        if c not in Str2:
            return False
    return True 

而且我相信这也是 O(N)。这是真的？哪种算法是有利的？作者的数据类型似乎是不必要的。

最后，这个算法是 O(NlogN) 吗？

def perm(str1,str2):
    return sorted(str1)==sorted(str2)

Answer 1

首先，作者的解决方案是Counter(str1) == Counter(str2)的优化版(它返回 False 更快，并创建一个 Counter 的实例)。它确实是 O(n)因为哈希表 ( Counter ) 访问是 O(1) .

接下来，您的解决方案是二次 ( O(n^2) ) 因为每个 in是O(n) - 它必须遍历整个字符串。对于重复的字符串也是错误的。

第三，sorted(str1) == sorted(str2)确实是线性的 ( O(n*log(n)) )因此比原来的线性解决方案更糟糕。

但是请注意，对于小 字符串，常量可能会产生一个差异和线性(sorted)解决方案可能会变成比线性 ( Counter) 更快。

最后，请注意 Python 通常是使用解释器实现的，因此实际性能可能取决于您使用的是用 C 还是用 Python 实现的功能。例如，如果 Counter用C实现，那么Counter(str1) == Counter(str2)很可能会优于作者的解决方案，即使算法作者的解决方案更好。