python - python代码的复杂性

Question

我试图找出这个 Python 程序的运行时复杂度。当我为每个递归调用创建一个新列表时，复杂度仍然是 n 还是会超过 n

def RecLinearSearch(lyst,number):
    found = False
    index = len(lyst)-1
    if lyst[index] == number:
        found = True
        return found
    elif index<len(lyst)-1:
        index +=1
        return RecLinearSearch(lyst[index:],number)
    return found
print(RecLinearSearch([1,4,5,65,44],55))

Answer 1

你的函数的时间和空间复杂度都是O(1)，因为index<len(lyst)-1总是假的。