遍历数组和对象的时间复杂度

Question

我有一个小型应用程序，其中有一组对象。每个对象都是一个学生，每个学生对象都有一个标签数组，如下所示：

const students = 
  [ { name: "John",   tags: [ 'tag1', 'tag2' ] } 
  , { name: "Leslie", tags: [ 'tag1' ]         } 
  , { name: "Mark",   tags: [ 'tag', 'tag2' ]  }
  ]

现在为了搜索具有相同标签的学生，我遍历了每个学生的对象数组和标签数组，这是 O(n) 的平方。

const filterByTag = (filter) => {
  let result = [];
  initialStudents.map((student) => {
    student.tags.map((tag) => {
      if (tag.includes(filter)) {
        result.push(student);
      }
    });
  });
  return result;
};

如何降低时间复杂度？我正在考虑创建一个带有 name->tags 的对象然后遍历它，但它似乎是相同的 O(n) 平方。

Answer 1

从复杂性的角度来看，我认为这里不会有任何重大进展。没有办法绕过

每个学生
每个学生里面的每个标签
每个标记字符串中的每个字符（抽象在.includes后面）

这需要大量的计算复杂性，您已经相当合理地实施了。

但是你可以让代码更好一点，减少一些不必要的开销。不要使用 .map 作为副作用 - 对于副作用，请使用 forEach 或 for..of。但是这里更好的方法是使用 .filter 来构造一个新的学生对象数组，具体取决于哪个学生通过了测试——因为您可能只想在匹配时推送一个学生，而不是每次匹配都推送该学生标签。

const filterByTag = (filter) => {
    return initialStudents.filter(student => 
        student.tags.some(
            tag => tag.includes(filter)
        )
    );
};

（仅当您将调用结果用作新数组时才使用 .map - 例如 const mappedArray = originalArray.map(...）

遍历数组和对象的时间复杂度

Time complexity of iterating through array and object

javascript

arrays

big-o

object