滑动窗口问题的时间复杂性

Question

我正在处理以下问题：

给定一个字符串和一个单词列表，查找给定字符串中所有子字符串的起始索引，这些子字符串是所有给定单词的一次完全串联，没有任何单词重叠。所有单词的长度都是一样的。例如：

输入：String=“catfoxcat”，Words=[“cat”，“fox”]
输出：[0,3]
说明：包含这两个单词的两个子字符串是“catfox”&；“狐猫”。

我的解决办法是：

def find_word_concatenation(str, words):
  result_indices = []
  period = len(words[0])
  startIndex = 0
  wordCount = {}
  matched = 0
  for w in words:
    if w not in wordCount:
      wordCount[w] = 1
    else:
      wordCount[w] += 1

  for endIndex in range(0, len(str) - period + 1, period):
    rightWord = str[endIndex: endIndex + period]
    if rightWord in wordCount:
      wordCount[rightWord] -= 1
      if wordCount[rightWord] == 0:
        matched += 1
    while matched == len(wordCount):
      if endIndex + period - startIndex  == len(words)*period:
        result_indices.append(startIndex)
      leftWord = str[startIndex: startIndex + period]
      if leftWord in wordCount:
        wordCount[leftWord] += 1
        if wordCount[leftWord] > 0:
          matched -= 1
      startIndex += period
      
  return result_indices

有谁能帮我弄清楚它的时间复杂性吗

Answer 1

我们应该首先区分代码的时间复杂度和实际需要的时间复杂度

在本例中，您有一组嵌套循环（一个for和一段时间）。所以，在最坏的情况下，也就是Big O所基于的情况下，当循环n次时，您将执行这些操作。但是你也有一个外循环，它也会被做n次

O（n）*O（n）=O（n）²

这不是很好。现在，虽然这个例子并没有那么糟糕，但想象一下，如果你在国会图书馆的所有图书馆，甚至在莎士比亚的文集中寻找“人是一件多么伟大的作品”

从好的方面来说，你可以重构你的代码，让它变得更简单