python - 尽管以下两个函数的时间复杂度似乎相似，但为什么性能却存在巨大差异？

Question

我正在尝试评估对数字列表进行排序的两种 Python 方法的性能。两者的时间复杂度似乎都是 n^2，但经验数据表明一个比另一个表现更好。这有什么原因吗？

我编写了两种方法，一种使用嵌套的 for 循环，另一种使用迭代查找最大值并将最大值添加到新列表(并从旧列表中删除)。

方法一:

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

方法二:

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 的时间复杂度似乎相同，为什么方法 2 的性能比方法 1 好得多？

Answer 1

本质上，正如评论所暗示的那样，它归结为 Python 在 C 中的主要实现。This answer指出真正的原因是C对应，列表操作的 native 实现max由于许多人优化代码，因此比您的 Python 实现快得多，并且通常，对于此类操作，C 的运行速度比 Python 快。
Here是“为什么 Python 程序通常比用 C 或 C++ 编写的等效程序慢？”这个问题的另一个答案。
从答案:

Internally the reason that Python code executes more slowly is because code is interpreted at runtime instead of being compiled to native code at compile time.

Other interpreted languages such as Java bytecode and .NET bytecode run faster than Python because the standard distributions include a JIT compiler that compiles bytecode to native code at runtime. The reason why CPython doesn't have a JIT compiler already is because the dynamic nature of Python makes it difficult to write one. There is work in progress to write a faster Python runtime so you should expect the performance gap to be reduced in the future, but it will probably be a while before the standard Python distribution includes a powerful JIT compiler.