Python 数学中 prod() 的时间复杂度是多少

Question

总结）

1. 时间复杂度是多少

   math.prod()

2. 如何改进此代码以达到通行证

详情）

目前正在 Leetcode

上研究“除自身之外的数组的乘积”

我的第一个代码是：

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        product_list = []

        for index in range(len(nums)):
            deleted_value = nums.pop(index)
            product_list.append(math.prod(nums))
            nums.insert(index, deleted_value)
            
        return product_list

并认为这是动态数组中的“删除和插入”导致时间限制问题。

所以，我将一些行更正为：

class Solution:
    def product_except_self(self, nums):
        product_list = []

        for index in range(len(nums)):
            temp = nums[index]
            nums[index] = 1
            product_list.append(math.prod(nums))
            nums[index] = temp

        return product_list

就我而言，“=”和附加操作的时间复杂度为 O(1)，因此认为 math.prod 是这里带来问题的地方，除了“for”，它是 O(n)。

请告诉我这里的时间复杂度以及一些通过此问题的技巧。

Answer 1

1. 几乎肯定是 O(n)；追加的时间复杂度为 O(1)，但会分摊到多次调用上。这取决于实现，但一些调用将不得不重新分配更大的内存并将迄今为止存在的所有内容复制到新空间中。

2. 这些挑战的目的是让您思考可以采取的更好方法，并练习学习以认识到您如何看待通常的方法以及通往更好方法的路径，以便您能够对一个不平凡的问题更容易进行这种思考。也就是说：您可以仅计算一次完整数组乘积，然后将该乘积除以每个数组元素以生成结果。使用生成器或列表理解。

Answer 2

我认为绕过时间限制的最佳方法是将值及其乘积存储在哈希表中，这样您就可以快速回答而不是再次计算该值