python - 递归字谜算法的大 O 复杂度

Question

我正在尝试使用递归方法 anagram() 返回字符串的所有排列。对于任何单词“ABCD...N”，该函数返回一个列表，该列表在 anagram("BCD...N") 中的尽可能多的位置上包含字母“A”。递归的限制情况是，如果参数大小为 2（例如：“XY”），则返回 ['XY','YX']。

代码如下：

def anagram(block):
   if (len(block) <= 2):
      permu=list()
      permu.append(block[0]+block[1])
      permu.append(block[1]+block[0])
   else:
      permu=list()
      lowerpermu=anagram(block[1:])             # anag(sd)
      for blocklet in lowerpermu:           # sd, ds are blocklets
         for each in rotate(block[0],blocklet):     # each in ['asd', 'sad', 'sda'] and ['ads', 'das', 'dsa']
            permu.append(each)
   return permu


def rotate(letter, word):
   rotatedlist=list()
   for i in range(len(word)+1):
      rotatedlist.append(word[:i]+letter+word[i:])
   return rotatedlist

def main():
   word=raw_input('Enter the word to be anagrammed: ')  #for example: 'asd'
   print anagram(word)                  

if __name__ == '__main__':
    main()

我正在自学一般算法及其分析，如果有人能提出一种经验法则来估计涉及递归的算法顺序，我将不胜感激。