arrays - 了解用于对数组中的元素求平方的大 O

Question

我正在研究一个问题，您必须在 leetcode 上对排序数组中的数字进行平方。这是原始问题

Given an array of integers A sorted in non-decreasing order, return an array of the squares of each number, also in sorted non-decreasing order.

我正在尝试理解我的代码和解决方案中给出的代码的大 O。

这是我的代码

def sortedSquare(A):
    new_A = []
    for num in A:
        num = num*num
        new_A.append(num)
    return sorted(new_A)


print(sortedSquare([-4, -1, 0, 3, 10]))

这是解决方案的代码:

def sortedSquares(self, A):
    return sorted(x*x for x in A)

对于解决方案，大O是

NlogN

其中 N 是数组的长度。我不明白为什么 Big O 会是 logN 而不仅仅是 N？

对于我的解决方案，我将其视为 N 中的大 O，因为我只是遍历整个数组。

此外，与给出的解决方案相比，我的解决方案是否是一个好的解决方案？

Answer 1

您的解决方案与给定解决方案的作用完全相同。两种解决方案都对所有元素进行平方，然后对结果数组进行排序，leetcode 解决方案更简洁一些。

这两个解决方案之所以都是O(NlogN)，是因为使用了sorted()。 Python 的内置排序是 timsort它在 O(NlogN) 时间内对数组进行排序。使用 sorted()，而不是平方，是时间复杂度的主要因素 (O(NlogN) + O(N) = O(NlogN)) .

请注意，尽管可以使用两个指针或使用合并排序中的合并步骤在 O(N) 中解决此问题。

编辑:

David Eisenstat 在 timsort 上提出了一个非常好的观点。 Timsort 聚合严格递增和严格递减的运行并合并它们。由于生成的平方数组将先严格递减，然后严格递增，timsort 实际上会反转严格递减的运行，然后将它们合并到 O(N) 中。