我编写了以下简单函数来检查
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
对于给定的输入,不能保证时间复杂度为 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
假设字典查找和字典更新都具有恒定的时间复杂度,
python字典是hashmap。 确切地说,在最坏的情况下,字典查找和更新的成本是
O(n)
。
is_perm2
的总平均时间复杂度为 O(n)
,但最坏情况时间复杂度为 O(n^2)
。
如果你想得到准确的
O(n)
时间复杂度,请使用List
(而不是Dictionary
)来存储字符的频率。
您可以轻松地将每个字符转换为 ascii 数字并将其频率存储到 python 列表中。