相关疑难解决方法(0)

def main():
    for i in xrange(10**8):
        pass
main()

Python中的这段代码运行(注意:时序是在Linux中的BASH中使用时间函数完成的.)

real    0m1.841s
user    0m1.828s
sys     0m0.012s

但是,如果for循环没有放在函数中,

for i in xrange(10**8):
    pass

然后它会运行更长的时间:

real    0m4.543s
user    0m4.524s
sys     0m0.012s

为什么是这样？

输入：

listi = [9, 7, 8, 4, 6, 1, 3, 2, 5]

输出：

# m=3
listo = [9, 8, 8, 6, 6, 3, 5]

给定一个由数字组成的随机列表n，我需要找到m连续元素的所有子列表，从子列表中选择最大值并将它们放入一个新列表中。

def convert(listi, m):
    listo = []
    n = len(listi)
    for i in range(n-m+1):
        listo.append(max(listi[i:3+i]))
    return listo

这个实现的时间复杂度是O(m\^{(n-m+1)}，如果很长的话就很糟糕了listi，有没有办法以 的复杂度来实现这个O(n)？