javascript - 关于 Javascript 原型(prototype)的范围求和查询问题(Leetcode)

Question

我无法弄清楚为什么下面这个问题的某些解决方案比其他解决方案执行得更快。我认为这与原型(prototype)关键字有关，但我无法立即理解为什么。

问题陈述链接:https://leetcode.com/problems/range-sum-query-immutable/

我通过以下方式解决了这个问题:

/**
 * @param {number[]} nums
 */
var NumArray = function(nums) {
        this.nums = nums;

};

/** 
 * @param {number} i 
 * @param {number} j
 * @return {number}
 */
NumArray.prototype.sumRange = function(i, j) {
            var sum = 0 ;
            for(; i <= j; i++){
                sum += this.nums[i];
            }
            return sum;
    };

/** 
 * Your NumArray object will be instantiated and called as such:
 * var obj = new NumArray(nums)
 * var param_1 = obj.sumRange(i,j)
 */

但是，在查看讨论部分后，这个答案会产生更快的结果:

function NumArray(nums) {
  this.sums = [];
  var sum = 0;
  for (var i = 0; i < nums.length; i++) {
    sum += nums[i];
    this.sums.push(sum);
  }
}

/** 
 * @param {number} i 
 * @param {number} j
 * @return {number}
 */


NumArray.prototype.sumRange = function(i, j) {
  return this.sums[j] - (i > 0 ? this.sums[i - 1] : 0);
};

我的答案的结果约为 21%，而第二个答案的结果约为 95%。我很困惑为什么它更快。

问题指出，在实例化 NumArray 对象后，对 sumRange 函数进行了多次连续调用。相比之下，我不明白为什么更多的调用会减慢我的代码。我在解决方案中读到它可能与缓存有关，但我不确定在这些解决方案的上下文中如何实现此类缓存。

谢谢。

Answer 1

每次调用 sumRange() 时，第一个版本都必须循环，因此时间复杂度为 O(n)。但创建 NumArray 对象的时间复杂度为 O(1)。

当您创建 NumArray 对象时，第二个版本仅循环一次，因此创建时间为 O(n)。但它的 sumRange() 版本利用了加法和代数变换的关联属性:

(nums[0] + nums[1] + nums[2] + nums[3]) == (nums[0] + nums[1]) + (nums[2] + nums[3])

因此

(nums[2] + nums[3]) == (nums[0] + nums[1] + nums[2] + nums[3]) - (nums[0] + nums[1])

由于 sums[i] 是 nums[0] + ... nums[i] 的总和，因此您可以使用以下方法计算任何子数组的总和那个区别。所以它不必循环，它的时间复杂度为 O(1)。

创建 NumArray 的较高成本会在您调用 sumRange() 的所有次数中摊销。