循环中常量数组切片的时间复杂度

Question

下面的代码的复杂度是多少？

我认为应该是O(N).

即使我们在O(K)中使用python的for循环内进行数组切片，它也将始终运行恒定时间，即等于pairLength。因此，例如，如果字符串的长度（即st为6而pairLength为3），则其总运行时间为6*3=12倍。同样，如果我们的st大小为12，它将运行36次。这就是混乱之处，我们也可以将其表示为O(N*M)，但是M始终是常数（一旦设置即pairLength），因此我们可以将其视为O(N)。正确吗？

edit：假设pairLength恒定且始终为3。那么复杂度是O（N）吗？

def writeAllCombinations(st, pairLength):
    for i in range((len(st)-pairLength)+1):
        print(st[i:i+pairLength]) # could also be done using inner loops and concat

下面的代码的复杂度是多少？我认为它将是O（N）。即使我们在使用O（K）的python的for循环中进行了数组切片，它也将始终运行恒定时间...

Answer 1

假设pairLength为常数，len（st）为N。显然，for循环运行N - pairLength + 1次= O（N）次。