这些置换算法的大O符号是什么

Question

通过“破解代码面试”和一道练习题

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)可能会比作者的解决方案更好，即使作者的解决方案在算法上更好。你知道吗

Answer 2

对于第一个代码，可以使用collection.Counter而不是循环：

def check_permutation(str1, str2):
    if len(str1) != len(str2):
        return False
    return Counter(str1) == Counter(str2)

又是O(n)。最后一个算法，因为有一个排序和使用sorted，它是O(nlogn)。你知道吗

您的算法不正确，因为您在另一个字符串中找到一个字符，而不考虑该字符的重复次数。如果这是真的，那就是O(n^2)。你知道吗

因此，在一般意义上，第一种算法具有最佳的时间复杂度和易于实现。你知道吗