javascript - 时间复杂度 : 3Sum algorithm under cubic time?

Question

我如何利用二分搜索来改进我的算法时间复杂度？

我正在审查一些面试的时间复杂度，但我在提高我的算法的时间效率方面遇到了麻烦。这是我对 3-Sum 问题的强力解决方案:有多少个三元组之和正好为 0？背景:我没有 CS 学位。

//BRUTE FORCE SOLUTION: N^3
var threeSum = function(list){
  var count = 0;

  //checking each triple
  for(var i = 0; i < list.length; i++){
    for(var j = i+1; j < list.length; j++){
      for(var k = j+1; k < list.length; k++){

        if(list[i] + list[j] + list[k] === 0){count++;}
      }
    }
  }
  return count;
};

//binary search code
var binarySearch = function(target, array){
  var lo  = 0;
  var hi  = array.length - 1;
  //base case
  while(lo <= hi){
    var mid = Math.floor( lo + (hi - lo) / 2 );
    if(target === array[mid]) return mid;
    if(target < array[mid]){
      hi = mid - 1;
    }
    if(target > array[mid]){
      lo = mid + 1;
    }
  }
  // value not found
  return -1;
}

我正在复习普林斯顿大学的在线算法类(class)，教授指出使用二分查找算法可以使该算法更加高效。

根据教授的说法，我们会:

• 排序列表
• 对于每对数字 array[ i ] & array[ j ] 二进制搜索 -(array[ i ] + array[ j ])

但是，我无法理解二分查找是如何解决问题的。这是讲座中的一张幻灯片，我仍在努力理解它，但可能对其他人有用:

我确信有几种有效的解决方案:请随时参与您的实现，因为它可能对我和其他 future 的读者有所帮助。谢谢

Answer 1

However, I'm having trouble understanding how binary search comes in to solve the problem.

这就是 n^2 log(n) 算法的工作原理:

1. 在 O(nlogn) 时间内对列表进行排序
2. 找到所有数字对 (i,j)，这是 O(n^2) 运行时间。
3. 然后，对于每一对 (i,j)，它找到一个数字 k，其中 k = sum - j - i。这是常数时间 O(1)
4. 该算法检查每个 k 是否存在，因为元组 (i,j,k) 的总和为 sum。为此，请执行二进制搜索，这需要 log(n) 时间。

最终运行时间为 O(nlogn) + O(logn * n^2) = O(n^2logn)

另一种(且更快)的解决方案是用哈希表替换排序部分。然后，查找值 k 将花费 O(1) 时间而不是 logn