寻找函数的复杂性

Question

我试图计算下一个函数max_list11的时间复杂度，该函数递归地查找列表的最大值：

def max11(L,left,right):
    if left==right:
        return L[left]
    return max(L[left], max11(L,left+1,right))

def max_list11(L):
    return max11(L,0,len(L)-1)

从我发现的情况来看，时间复杂度应该是O(n)，因为函数所做的是n乘以2个对象列表的最大值，尽管当我计算运行时间时，我得到了运行时间的多项式增长（显然是O(n²)），我想知道这是为什么。你知道吗

我用这种方法计算函数的时间：

def elasped(f,L):
    t0 = time.clock()
    s = f(L)
    return(time.clock()-t0)

def avg_elasped(f,L,times = 100):
    measurements = []
    for i in range(times):
        measurements += [elasped(f,L)]
    return sum(measurements)/times

然后我试了1000，2000。。。。，10000个长列表。你知道吗

Answer 1

递归方法将每次调用的输入大小减少一个，因此理论上是线性的（因为实际上是线性搜索最大值）。Python列表的实现将扭曲基于计时器的分析。你知道吗

Answer 2

它是线性的：

%timeit max_list11(range(10))
100000 loops, best of 3: 6.93 µs per loop

%timeit max_list11(range(100))
10000 loops, best of 3: 66.7 µs per loop

%timeit max_list11(range(1000))
1000 loops, best of 3: 775 µs per loop

%timeit max_list11(range(10000))
100 loops, best of 3: 9.82 ms per loop

始终使用timeit.default_timer()作为时间戳。或者像我对这个输出所做的那样。time.clock()根据您的操作系统有不同的含义。从docs：

On Unix, return the current processor time as a floating point number expressed in seconds. The precision, and in fact the very definition of the meaning of “processor time”, depends on that of the C function of the same name.

On Windows, this function returns wall-clock seconds elapsed since the first call to this function, as a floating point number, based on the Win32 function QueryPerformanceCounter(). The resolution is typically better than one microsecond.