Python分片复杂度？

Question

这个短程序的时间复杂度是多少？我觉得是线性的，但话说回来，在if语句里有一个Python分片。我想知道它对复杂度有什么贡献？

def count_s(string, sub):

  i = 0
  j =len(sub)-1
  count = 0

  while j < len(string):
      if string[i:j+1] == sub:
          count = count + 1
          j = j + 1
          i = i + 1
      else:
          i = i + 1
          j = j + 1

  return count

Answer 1

Python的时间复杂度是O(k)，其中k是分片的长度，所以你的函数是O(n * k)，这不是线性的，但仍然不是指数的。另一方面，你可以使用Python内置的计数函数，如是。string.count(sub).

或者，如果你打算使用自己的代码，为了可读性，也可以将其缩减为这样。

def count_s(string, sub):
    i = count = 0
    j = len(sub) - 1

    while j < len(string):
        count += string[i:j + 1] == sub
        j += 1
        i += 1

    return count