Python 时间复杂度将 O(n^2) 代码转换为 O(n)

Question

递归函数dumbo_func已预加载到答案框中，具有O(n^2)性能。重写它（仍然使用递归），使其性能变为 O(n)。您的函数将在一个循环中进行测试，调用它 20 次，列表最多包含 10,000 个元素，如果函数仍然是 O(n^2 )，则会超时。

请注意，该函数前面有代码以增加最大值 递归深度。您在执行操作时需要包含该代码 自己的测试以及提交答案时。然而，在微软的领导下 Windows 如果你尝试列表，Python 解释器可能会崩溃 约2000多种元素。在实验室机器上或测验中 服务器，列表大小为 10,000 就可以了，前提是您已经创建了 对代码进行必要的更改，使其时间复杂度为 O(n) 而不是 O(n2)。

import sys
sys.setrecursionlimit(100000)

def dumbo_func(data):
    """Takes a list of numbers and does weird stuff with it"""
    if len(data) == 0:
        return 0
    else:
        if (data[0] // 100) % 3 != 0:
            return 1 + dumbo_func(data[1:])
        else:
            return dumbo_func(data[1:])

#Test1
#Simple test with short list.
#Original func works fine on this
#Result: 3
data = [677, 90, 785, 875, 7, 90393, 10707]  
print(dumbo_func(data)) 


#Test2
#This test will timeout with a O(n^2) function
#Result: Yay!
ok = True
for i in range(20):
    # Repeat enough times to ensure timeout on O(n^2)
    data = list(range(10_000))
    right_ans = secret_version(data)
    your_ans = dumbo_func(data)
    if your_ans != right_ans:
        print("Sorry, but no banana")
        ok = False
        break
if ok:
    print("Yay!")

我编写的代码如下，它通过了 test1 但未通过 test2。我的代码不是 O(n) 吗？不当之处请多多指教。

import sys
sys.setrecursionlimit(100000)

def dumbo_func(data):
    """Takes a list of numbers and does weird stuff with it"""
    if len(data) == 0:
        return 0
    else:
        return int((data[0] // 100) % 3 != 0) + dumbo_func(data[1:])

Answer 1

这是关于列表切片的简单指南。长话短说，递归函数的复杂度为 O(N^2)，因为每次对列表进行切片以递归调用函数时，每个切片都需要 O(N) 时间。

解决方案：尝试将您正在考虑的子数组的第一个元素的索引发送给递归函数，而不是发送整个切片数组作为参数。

提示：def func(data, index_of_first_element) 而不是 def func(data)

Answer 2

我尝试将索引发送到子数组，但时间限制超出了 [0]*10000

import sys
sys.setrecursionlimit(100000)

def dumbo_func(data, start_index=0):
    """Takes a list of numbers and does weird stuff with it"""
    if len(data) - start_index == 0:
        return 0
    else:
        if (data[start_index] // 100) % 3 != 0:
            return 1 + dumbo_func(data, start_index+1)
        else:
            return dumbo_func(data, start_index+1)

data = [677, 90, 785, 875, 7, 90393, 10707]
print(dumbo_func(data))
data = [0]*10000 
print(dumbo_func(data))