排序数组的平方，为什么Sorted（）方法比O（n）方法快？

Question

我正在研究leetcode算法问题977. Squares of a Sorted Array.

为什么使用内置排序方法的提交要比下面的o（n）遍历方法快？你知道吗

输入是带有整数的排序（非降序）列表。你知道吗

提交样品：

class Solution:
    def sortedSquares(self, A: List[int]) -> List[int]:
        return sorted(x*x for x in A)

我的260毫秒提交：

class Solution:
    def sortedSquares(self, A: List[int]) -> List[int]:
        start = 0
        end = len(A)-1

        B = []

        while start <= end:
            if abs(A[start]) >= abs(A[end]):
                B.append(A[start] * A[start])
                start += 1
            else:
                B.append(A[end] * A[end])
                end -= 1
        B.reverse()
        return B

Answer 1

仅仅因为你的算法有更好的最坏情况运行时间并不意味着它在实践中会更好。Python的内置排序方法是高度优化的，因此对于相对较小的c，它的运行时间可以是cnlg(n)，而您的算法虽然是O(n)，但是对于dn，它的常数d非常高。我们不知道您的输入是什么，所以它可能是一个由10000个元素组成的数组，对于这个数组，d仍然比clg(10000)大很多。你知道吗

另外，由于您的输入列表是排序的（非负部分），在这种情况下，可能会对几乎排序的列表进行一些优化（不确定，从来没有看过Python的排序实现）。你知道吗

Answer 2

这是因为Python使用Timsort，这是一种基于marge\u排序和insertion\u排序的自适应排序算法。时间复杂度是

O(nlogn)

用于python中的Sorted（）。你知道吗

这就是为什么你的工作比你的快

Answer 3

您可以对所有内容进行预平方处理（因此不需要abs()，尤其不需要对单个元素重复abs()调用）：

C = [x*x for x in A]

start = 0
end = len(A)-1

B = []

while start <= end:
    if C[start] >= C[end]:
        B.append(C[start])
        start += 1
    else:
        B.append(C[end])
        end -= 1
B.reverse()
return B

但我没量过。例如，就地预平方可能会表现更好。你知道吗