循环遍历数组的时间复杂度加上 arr.indexOf() 另一个数组

Question

我有以下函数，但我不能 100% 确定它的时间复杂度。该函数的目的是 return arr 的统一版本。函数遍历arr，检查它是否存在于uniqueObjects数组中（arr是一个对象数组，我们不想删除副本，我们只想删除重复的对内存中同一对象的引用）。

function uniquifyArray(arr) {
    var uniqueObjects = [];
    for(i=0; i<arr.length; i++) {
    if(uniqueObjects.indexOf(arr[i])==-1) {
            uniqueObjects.push(arr[i]);
    }
  }
  return uniqueObjects;
}

我能推断出的最好的情况是时间复杂度为 O(n+m)，其中 n 是 arr 的大小，m 是 [=15] 的大小=].我知道 uniqueObjects.indexOf() 是 O(n) 但我不确定的是，在我们完全遍历所有 [=13] 之前，我们不能 100% 确定 uniqueObjects 的大小=]. uniqueObjects 是一个可能会随着每次迭代而增长的数组。

假设您是这样调用函数的：

var objects = [
    {id:1}, //unique in memory
    {id:2}, //unique in memory
    {id:3}, //unique in memory
    {id:1}  //reference in memory to object at objects[0]
    {id:2}  //reference in memory to object at objects[1]
];
var uniqueObjects = uniquifyArray(objects);
/*
 * uniqueObjects = [
 *    {id:1},
 *    {id:2},
 *    {id:3}
 * ]
 */

虽然我不介意看到更有效的解决方案，但我想弄清楚我上面编写的函数的复杂性。

谢谢！

Answer 1

复杂度为 O(n^2)，其中 n 是 arr 的长度。

for循环是时间O(n)，其中n是arr的长度。在循环的每一次迭代中，都会调用uniqueObjects.indexOf(...)，也就是时间复杂度O(m)，其中m是uniqueObjects的长度。

因此，整体时间复杂度为O(nm)。但是，这可以简化为 O(n^2)，因为 m 的上限为 n。

Answer 2

那就是 O(N2)。使其成为 O(N) 的一种简单方法是使用 Map 而不是 Array 来跟踪唯一对象，从而使查找 O(1).

var o1 = { id: 1 }, 
    o2 = { id: 2 },
    objects = [o1, o1, o2, o2, o2];

alert(uniquifyArray(objects).length);

function uniquifyArray(arr) {
  
  var objMap = new Map();
  
  return arr.filter(function (obj) {
    if (!objMap.has(obj)) {
      objMap.set(obj, true);
      return true;
    }
    
    return false;
  });  
}

Answer 3

您可以使用对象本身，临时属性，它在最后一个循环中被删除。复杂度 O(n+m).

function uniquifyArray(arr) {
    var uniqueObjects = arr.filter(function (a) {
        if (!a.___) {
            a.___ = true;
            return true;
        }
    });
    uniqueObjects.forEach(function (a) {
        delete a.___;
    });
    return uniqueObjects;
}

var id1 = { id: 1 }, id2 = { id: 2 }, id3 = { id: 3 },
    objects = [id1, id2, id3, id1, id2, id3, id1],
    uniqueObjects = uniquifyArray(objects);

console.log(uniqueObjects);

循环遍历数组的时间复杂度加上 arr.indexOf() 另一个数组

Time complexity of loop over an array plus arr.indexOf() another array

javascript

big-o

time-complexity