尽管下面两个函数的时间复杂度似乎相似，但为什么性能会有巨大差异？

Question

我正在尝试评估对数字列表进行排序的两个Python方法的性能。两者的时间复杂度似乎均为n ^ 2，但经验数据表明，其中一个的性能优于另一个。有什么原因吗？

我写了两种方法，一种使用嵌套的for循环，另一种方法是找到一个最大值并将该max迭代添加到新列表中（并从旧列表中删除）。

方法1：

def mysort1(l):
    i = 0
    j = 1
    for i in range(0,len(l)-1):
        for j in range(i,len(l)):
            if l[i] > l[j]:
                tmp = l[j]
                l[j] = l[i]
                l[i] = tmp
    return l

方法2：

def mysort2(l):
    nl = []
    for i in range(0,len(l)):
        m = max(l)
        nl.insert(0, m)
        l.remove(m)
    return nl

两者均以相反的顺序用10000个数字进行了测试。使用配置文件时，方法1大约需要8秒（10000次以上的调用），方法2仅需要0.6秒（30000次以上的调用）。尽管两种方法的时间复杂度相同，但为什么方法2的性能比方法1更好的任何原因？

Answer 1

Python 没有给出关于时间复杂度的#@&^（当然有，但是......）

Python 是解释型动态类型语言，在类型检查和运行时“编译”上有大量时间开销。例如，在您的第一个方法中，它必须检查i每次迭代的类型至少六次（在索引列表时）。

所以我假设处理时间差异是因为max经过优化并且（因为您可能使用 CPython 解释器）基本上是一个 C 函数（以及.insert方法.remove）。