python - 滑动窗口问题的时间复杂度

Question

我正在解决以下问题：

给定一个字符串和一个单词列表，找到给定字符串中的所有子字符串的起始索引，这些子字符串是所有给定单词的串联一次，没有任何单词重叠。假设所有单词的长度相同。例如：

输入：String = "catfoxcat", Words = ["cat", "fox"]
输出：[0, 3]
解释：包含两个单词的两个子字符串是 "catfox" 和 "foxcat"。

我的解决方案是：

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

谁能帮我弄清楚它的时间复杂度吗？

标签： pythonsubstringtime-complexitysliding-window

Answer 1

我们应该首先区分代码的时间复杂度与您可能实际寻找的时间复杂度。

在您的情况下，您有一组嵌套循环（for 和 while）。因此，最坏的情况，即 Big O 所基于的，您将执行每个 while 循环n次。但是你也有那个外循环，它也会被做n次。

O(n) * O(n) = O(n) ²

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

从好的方面来说，你可以重构你的代码并把它降低很多。