代码之家 › 专栏 › 技术社区 › AnonymousSB

避免重复计算以优化嵌套for循环的时间复杂性

big-o optimization loops algorithm javascript

AnonymousSB · 技术社区 · 6 年前

今天,我用下面的代码对HackerRank进行了一个简单的挑战,这是100%可以接受的,并且有效,但是我想知道是否有一种方法可以通过消除重复计算来进一步减少所需的循环。

k = 3 .

在一个由6个数字组成的数组中,这相当于15个循环 O(nÂ²) ,这意味着我的循环将随着输入量呈指数增长。7个数字等于21个循环。

另外,你可能会认为6应该是21个循环,7应该是28个循环,但是请记住,我总是把当前的数字加在下一个数字上,除了最后一个数字。

视觉故障

input: [1, 3, 2, 6, 1, 2]

1+2 1+2
3+6 , 3+1 , 3+2
2+1
,
1+2

如果你看看我输入的数字 大胆的 ,您将看到它们是重复的计算。这个数字是可以被数整除的数字 . 现在我们开始讨论我的问题。我怎样才能消除这个重复的数学,在这个特殊的例子中,它会使我的循环从15降到8。该算法仍然会出现更糟糕的情况,即 O(n)

function divisibleSumPairs(k, a) {
  let pairs = 0;
  for (let i = 0; i < a.length - 1; i++) {
    for (let j = i + 1; j < a.length; j++) {
      if ((a[i] + a[j])/k % 1 === 0) pairs++;
    }
  }
  console.log(pairs);
}

divisibleSumPairs(3, [ 1, 3, 2, 6, 1, 2 ])

2 回复 | 直到 6 年前

AnonymousSB 6 年前

然后我想“如果我预处理除数呢”?

这种方法的缺点是,它创建和除数大小相同的数组,但它是在 O(n) 时间复杂度(螺旋空间复杂度,lol)

O(nÂ²) .

O(n)

function divisibleSumPairs(k, a) {
  const mod = new Array(k).fill(0);
  let pairs = 0;
  
  for (let i = 0; i < a.length; i++) {
      const position = a[i] % k;
      
      pairs += mod[(k - position) % k];
      mod[position]++;
  }
  
  console.log(pairs);
}

divisibleSumPairs(3, [ 1, 3, 2, 6, 1, 2 ])

性能测试

for 循环比较 forEach 和 reduce .

for^2
对于 :此帖子中的代码
弗雷奇 相反
减少 :此帖子使用 减少

https://jsperf.com/for-2-vs-for-vs-foreach-vs-reduce/1

warl0ck 6 年前

要实现这个动态问题

尝试将结果存储在 Object 比方说 sum_map

示例代码段:

let d = [1, 3, 2, 6, 1, 2]

const len = d.length

const sum_map = {}

let pairs = 0

for (let i = 0; i < d.length - 1; i++) {
  for (let j = i + 1; j < d.length; j++) {
    const key1 = `${d[i]}_${d[j]}`
    const key2 = `${d[j]}_${d[i]}`
    let result = 0
    if (sum_map[key1]) {
      result = sum_map[key1]
    } else if (sum_map[key2]) {
      result = sum_map[key2]
    } else {
      result = d[j] + d[i]
      sum_map[`${d[i]}_${d[j]}`] = result
    }
    if (result % 3 === 0) {
      pairs += 1
    }
  }
}
console.log(pairs)

为了避免O(n^2),一个简单的技巧就是知道

只有当数与余数相等时,才能找到可被数整除的和。

3 % 5 = 2 和 2 % 5 = 3

比如说你是3个num,剩下2个,4个num,剩下3个

若这个数可以被5整除,但若它只有1,那个么它的和永远不会被整除。

代码段:

let d = [1, 3, 2, 6, 1, 2, 5]

const check_div_num = 5

remainder_map = {}

mod_arr = d.map((i) =>{
  const rem = i % 5
  if(remainder_map[rem]) {
    remainder_map[rem] += 1
  } else {
    remainder_map[rem] = 1
  }
  return rem
})

const till = Math.floor(check_div_num / 2)

keys = Object.keys(remainder_map)


let pairs = 0

for (let j = 0; j < keys.length; j++) {
  const key = keys[j]
  if(key === '0' && remainder_map["0"] > 1) {
    pairs += remainder_map[key] / 2
    continue
  }
  if(Number(key) <= till) {
    let compliment = remainder_map[check_div_num - Number(key)]
    const compliemnt_key = check_div_num - Number(key)
    if(compliment) {
      pairs += remainder_map[key]*remainder_map[compliemnt_key.toString()]
    } else {
      continue
    }
  } else {
    break
  }
}
console.log(pairs)