两种算法的时间复杂度分析与经验结果相矛盾

Question

我编写了以下简单函数来检查

str1

是否是

str2

的排列：

def is_perm(str1, str2):
    return True if sorted(str1)==sorted(str2) else False
    

假设

sorted(str)

的时间复杂度为

O(n*logn)

，我们可以预期时间复杂度为

O(2*n*logn)=O(n*logn)

。以下函数尝试实现更好的时间复杂度：

def is_perm2(str1, str2):
    dict1 = {}
    dict2 = {}
    
    for char in str1:
        if char in dict1:
            dict1[char] += 1 
        else:
            dict1[char] = 1
    for char in str2:
        if char in dict2:
            dict2[char] += 1         
        else:
            dict2[char] = 1
        
    if dict1==dict2:
        return True
    else:
        return False
    

每个 for 循环迭代 n 次。假设字典查找和字典更新都具有恒定的时间复杂度，我预计整体复杂度为

O(2n)=O(n)

。然而，

timeit

测量结果显示出以下相互矛盾的结果。为什么在 1000000 次执行后

is_perm2

比

is_perm

慢，尽管它的时间复杂度看起来更好？我的假设有错吗？

import timeit

print(timeit.timeit('is_perm("helloworld","worldhello")', 'from __main__ import is_perm', number=10000000))
print(timeit.timeit('is_perm2("helloworld","worldhello")', 'from __main__ import is_perm2', number=10000000))

# output of first print-call: 12.4199592999993934 seconds
# output of second print-call: 37.13826630001131 seconds

Answer 1

对于给定的输入，不能保证时间复杂度为 O(nlogn) 的算法会比时间复杂度为 O(n) 的算法慢。例如，第二个可能具有较大的恒定开销，使得输入大小低于 100000（例如）时速度变慢。

在您的测试中，输入大小为 10（“helloworld”），这并不能告诉我们太多信息。即使重复 10000000 次，重复该测试也不会产生任何影响。重复只能更准确地估计在该特定输入上花费的平均时间。

您需要为算法提供越来越大的输入。如果内存允许，这将最终使我们达到 O(nlogn) 算法比 O(n) 算法花费更多时间的输入大小。

在这种情况下，我发现输入大小与可用内存相比必须非常大，并且我勉强找到了显示差异的情况：

import random
import string
import timeit

def shuffled_string(str):
    lst = list(str)
    random.shuffle(lst)
    return "".join(lst)

def random_string(size):
    return "".join(random.choices(string.printable, k=size))

str1 = random_string(10000000)
str2 = shuffled_string(str1)
print("start")
print(timeit.timeit(lambda: is_perm(str1, str2), number=5))
print(timeit.timeit(lambda: is_perm2(str1, str2), number=5))

初始设置字符串（每个字符串的大小为 1000 万个字符）后，我得到以下输出：

54.72847577700304
51.07616817899543

输入必须如此大才能看到这种情况发生的原因是

sorted

在较低级别的编译代码（通常是 C）中完成所有艰苦的工作，而第二个解决方案则完成所有循环和字符读取在Python代码中（通常是解释的）。很明显，与第一个解决方案相比，第二个解决方案的开销是巨大的。

改进第二个解决方案

虽然不是你的问题，但我们可以通过依赖另一个内置函数来改进第二种算法的实现：

Counter

:

def is_perm3(str1, str2):
    return Counter(str1) == Counter(str2)

通过与上面设置相同的测试，我得到了这个实现的时间：

24.917681352002546

Answer 2

假设字典查找和字典更新都具有恒定的时间复杂度，

python字典是hashmap。 确切地说，在最坏的情况下，字典查找和更新的成本是

O(n)

。

is_perm2

的总平均时间复杂度为

O(n)

，但最坏情况时间复杂度为

O(n^2)

。

如果你想得到准确的

O(n)

时间复杂度，请使用

List

（而不是

Dictionary

）来存储字符的频率。 您可以轻松地将每个字符转换为 ascii 数字并将其频率存储到 python 列表中。