大O复杂度算法

Question

我只是在学习Big符号，我已经经历了几个思考的谜题，我只是想和人们验证我是否正确地思考问题。

在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;
} 

findCommon(1，2，4，6，7，3，4，5，7) ->4，7

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)。

Answer 2

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