时间戳

首页 > 解决方案 > 查找所有子字符串的时间复杂度是多少？

recursion - 查找所有子字符串的时间复杂度是多少？

问题描述

我制作了这段代码来生成给定字符串的所有唯一子字符串，当我使用递归时，我很难找到代码的复杂性。我认为这个问题的时间复杂度是 O(N²)，但是我的复杂度是多少，如何改进我的代码？

'''
          a            b          c    d 
       ab ac ad      bc bd      cd
     abc abd acd   bcd
   abcd

'''
dict_poss = {}

#get all letters
def func(string):
    for i,value in enumerate(string):           
        dict_poss[value] = True 
        recursive(value,string[i+1:])   

#get all combinations
def recursive(letter,string):   
    for i,value in enumerate(string):           
        if letter+value not in dict_poss:
            dict_poss[letter+value] = True;
        recursive(letter+value,string[i+1:])    
    return  

func("abcd")
print(dict_poss)

标签： recursiontime-complexity

解决方案

根据您在顶部写的内容，您试图找到字符串的所有可能子序列，在这种情况下，这将是 O(2^n)。考虑长度为 N 的可能二进制字符串的数量，您可以在其中通过每个可能的二进制字符串的掩码构造一个子序列（如果为 1，则取一个字母，如果为 0，则忽略它）。

如果您想找到所有可能的子字符串，这归结为您使用的语言中字符串的实现。在 c++ 中，执行 n^2 相当简单，但在 java 中它会是 O(n^3)，因为子字符串 / 连接是 O(n) （虽然你可以在 java 中的 n^2 中做到这一点，但只需要对你所做的事情很棘手:))。不知道它是什么，我猜这是python（如果你包含代码，你应该用你使用的语言标记你的问题），但你可以查一下。您也可以使用不同大小的输入对其进行计时，获得复杂度为 n^2 的可测量运行时并不难。

推荐阅读