寻找函数的复杂性

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() 作为时间戳。或者 IPython 就像我对这个输出所做的那样。 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.

寻找函数的复杂性

Finding the complexity of a function

python

complexity-theory

max

time-complexity