performance - 字符串连接检查算法的运行时

Question

我编写了一个算法来检查一个字符串是否是数组中任意数量的字符串的串联（同时能够多次使用一个字符串）。我很难弄清楚算法的运行时间到底是什么。

我针对数组中的每个单词检查有问题的字符串，当我找到一个从索引 0 开始的原始字符串的子字符串的单词时，我也会针对数组中的每个单词检查剩余的子字符串。所以我认为这是一个 O(n^n)，除非我遗漏了什么。

def check_concat(str,substr,words)
  if substr == ""
    return false
  end

  words.each do |word|
    if word == substr && str != substr
      return true
    end
    if substr.index(word) == 0
      if check_concat(str,substr[word.length..-1],words)
        return true
      end
    end
  end
  return false
end

Answer 1

让我们假设您的主字符串包含m words并且n words在要搜索的数组中有。在最坏的情况下，您需要检查主字符串中的每个单词与数组中的每个单词，即mn时间。因此函数的时间复杂度为O(mn)。

例如主字符串 be "Hello Hello Hello Hello Hello"。要检查的数组包含以下单词'Hai', 'Fine', 'Hello'。然后该函数将需要总共 15 次比较。