大O复杂度算法

Question

我刚开始学习大O符号，做了一些思维题，想向大家确认我的思路是否正确。

在Javascript中，如果通过两个数组查找共同的元素，这是否被认为是O（n）时间复杂度的解决方案？或者该语言是否会在对象内执行查找并以与迭代数组相同的方式迭代对象中的n个元素？

function findCommon (input, input2){
  var key = {};
  var out = [];
  for(var i=0; i<input.length; i++){
    key[input[i]] = true;
  }
  for(var j=0; j<input2.length; j++){
    if(key[input2[j]] == true){
      out.push(input2[j]);
    }
  }
  return out;
} 

查找公共元素([1, 2, 4, 6, 7], [3, 4, 5, 7]) --> [4, 7]

- Vincent Chan

---

它的时间复杂度是O(n)。至于JS的问题：这不是你代码的问题，是吗？（实际上，我相信他们使用比普通线性数组更好的数据结构） - deviantfan

你几乎回答了我的关于JS数据结构的问题。可以说对象是在一组数据中执行查找的最佳数据结构吗？还是这取决于编程语言？ - Vincent Chan

是的，这取决于语言（因为有很多没有对象的语言）和您的JS引擎... - deviantfan

Answer 1

让 m 为 input 的长度，n 为 input2 的长度。第一个循环的复杂度是 O(m)，第二个循环的复杂度是 O(n)。每当你面对顺序代码时，复杂度会被相加（如果循环嵌套而不是顺序，则它们将被相乘），从而得到总的复杂度为 O(m + n)，这是确切的上限，并且显然与参数大小成线性关系。

现在，m + n <= 2 * max(m, n)，因此您可以说该函数也是 O(2 * max(m, n))，但我们当然可以去掉常数，这样就给出了 O(max(m, n))。让我们假设 n 总是大于 m（这没什么大不了的，因为它并没有太大改变）。这使得我们得到 O(n)，因此确实可以说该算法是 O(n)，但更精确的表示法是 O(m + n)。

- Nikola Dimitroff

Answer 2

您的函数由两个O(n) 复杂度组成。因此，您的函数的总复杂度为O(n)。如在评论中所提到的，我想澄清您有两个不同的O(n) 和 O(m) ，它们不等于O(2n)（但您仍然会删除所有常数）。但在您的情况下，这并不重要，因为复杂度不取决于m或n 的大小，而是取决于结构的复杂度（在您的情况下是单个for循环）。

- Sergey Tsibel

---

我认为正式来讲，你需要额外解释一下：你有两个长度分别为 n 和 m 的输入，并且假设较长的那个总是 n。有了这个假设，你可以近似认为时间复杂度是 O(2n) = O(n)。 - xjedam