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

Question

下面代码的复杂性是什么

在我看来，这将是O(N).

尽管我们在for循环中有数组切片，它在python中使用O(K)，但它总是以恒定的时间运行，即等于pairLength。例如，如果字符串的长度，即st是6，而pairLength是3，那么它运行的总次数是6*3=12次。类似地，如果我们有大小为12的st，它将运行36次。这里是混乱，我们也可以说它是^ {CD8}}，但是M总是常数（一旦设置，即成对长度），所以我们可以把它看作^ {CD9}}。对吗

编辑：让我们假设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

# calling function
writeAllCombinations("HelloWorld", 3)

Answer 1

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

在for循环的每个步骤中， 假设st是一个列表，那么st[i:i+pairLength]需要O（1）个时间^在这种情况下，{}也可以假定为O（1）时间

因此，我们可以得出结论，函数需要O（N）时间