我正在学习一些python，在这个过程中，我正在做一些来自代码战争的简单卡塔。我碰到https://www.codewars.com/kata/scramblies问题
我的解决方案如下：
def scramble(s1,s2):
result = True
for character in s2:
if character not in s1:
return False
i = s1.index(character)
s1 = s1[0:i] + s1[i+1:]
return result
虽然这是正确的结果，但速度不够快。我的解决方案在12000毫秒后超时。我看了其他人提出的解决方案，其中一个涉及制作一套。
def scramble(s1,s2):
for letter in set(s2):
if s1.count(letter) < s2.count(letter):
return False
return True
为什么我的解决方案比另一个慢得多？它看起来不应该是这样的，除非我误解了切片字符串的效率。我解决这个问题的方法是有缺陷的还是不符合常理？
对于这种对程序运行时间有限制的在线编程挑战，测试输入将包括一些相当大的示例，并且通常会设置时间限制，这样你就不必从代码中挤出最后一毫秒的性能，但你必须写一个计算复杂度足够低的算法。为了回答您的算法超时的原因，我们可以使用大O符号对其进行分析，以找出其计算复杂性。
首先，我们可以用每个单独的语句的复杂性来标记它，其中n是s1的长度，m是s2的长度：
def scramble(s1,s2):
result = True # O(1)
for character in s2: # loop runs O(m) times
if character not in s1: # O(n) to search characters in s1
return False # O(1)
i = s1.index(character) # O(n) to search characters in s1
s1 = s1[0:i] + s1[i+1:] # O(n) to build a new string
return result # O(1)
则总复杂度为O(1+m*(n+1+n+n(+1(或更简单地为O(m*n(。这对于这个问题是无效的。
替代算法更快的关键在于set(s2)只包含字符串s2中的不同字符。这一点很重要，因为形成这些字符串的字母表具有恒定的、有限的大小；小写字母大概是26。考虑到这一点，替代算法的外循环实际上最多运行26次：
def scramble(s1,s2):
for letter in set(s2): # O(m) to build a set
# loop runs O(1) times
if s1.count(letter) < s2.count(letter): # O(n) + O(m) to count
# chars from s1 and s2
return False # O(1)
return True # O(1)
这意味着替代算法的复杂度是O(m+1*(n+m+1(+1(，或者更简单地说是O(m+n(，这意味着它渐近地比你的算法更有效。
首先，set速度快，非常擅长它的工作。对于像in这样的东西，set比list快。
其次，您的解决方案比正确的解决方案做更多的工作。请注意，第二个解决方案从不修改s1或s2，而您的解决方案都采用s1的两个切片，然后重新分配s1。这与调用.index()。切片不是最快的操作，主要是因为必须分配内存和复制数据。.remove()可能比您正在进行的.index()和切片的组合更快。
这里的基本信息是，如果任务可以在更少的操作中完成，那么它显然会执行得更快。切片也比大多数其他方法更昂贵，因为分配空间和复制内存比正确解决方案使用的.count()等计算方法更昂贵。