如何提高这个片段的时间复杂度？

Question

我正在努力提高下面代码片段的时间复杂度和质量。我正在遍历一个数组以检查该数组中的元素是否存在于对象中，如果是这样，它应该 return 名称与对象中的元素 id 匹配。如果没有嵌套循环，我该怎么做？有人可以告诉我如何改进这个算法吗？

提前谢谢大家。

let genres = [28, 12, 878];
data = {
  genres: [
    {
      id: 28,
      name: 'Action',
    },
    {
      id: 12,
      name: 'Adventure',
    },
    {
      id: 16,
      name: 'Animation',
    },
    {
      id: 35,
      name: 'Comedy',
    },
    {
      id: 80,
      name: 'Crime',
    },
    {
      id: 99,
      name: 'Documentary',
    },
    {
      id: 18,
      name: 'Drama',
    },
    {
      id: 10751,
      name: 'Family',
    },
    {
      id: 14,
      name: 'Fantasy',
    },
    {
      id: 36,
      name: 'History',
    },
    {
      id: 27,
      name: 'Horror',
    },
    {
      id: 10402,
      name: 'Music',
    },
    {
      id: 9648,
      name: 'Mystery',
    },
    {
      id: 10749,
      name: 'Romance',
    },
    {
      id: 878,
      name: 'Science Fiction',
    },
    {
      id: 10770,
      name: 'TV Movie',
    },
    {
      id: 53,
      name: 'Thriller',
    },
    {
      id: 10752,
      name: 'War',
    },
    {
      id: 37,
      name: 'Western',
    },
  ],
};

const getGenreName = () => {
  let result = [];
  for (let genre of data.genres) {
    //console.log("genre", genre.name)
    for (let id of genres) {
      //console.log('id',genres[i])
      if (id === genre.id) result.push(genre.name);
    }
  }
  console.log(result);
};

getGenreName();

Answer 1

最简单的改进可能是将 genres 转换为集合 https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set 并使用 has 方法检查数据中的每个 id 是否属于所选流派集。

您还可以将数据转换为以 id 为键的映射，以便通过 id 快速查找而不是循环，但只有在多次重复使用数据时才会更快。

Answer 2

下面概述的示例中的

JavaScript #reduce 将具有 O(n) 时间复杂度。这只循环遍历数组一次。我们可以使用 filter 和 map，但这会导致我们不得不遍历数组两次。

const getGenreName = () => {
    const genreSet = new Set(genres);
    return data.genres.reduce((accumulator, { id, name }) => {
        if (genreSet.has(id)) accumulator.push(name);
        return accumulator;
    }, []);
};

console.log(getGenreName()); // [ 'Action', 'Adventure', 'Science Fiction' ]

我们正在初始化 reducer 以数组 [] 或空数组开始，然后检查对象的 genre 属性是否包含在genres 数组，如果不是，return 累加器，如果是，则将其附加到累加器的末尾并 return 它。

Answer 3

你想要一个循环，所以这里是：

let result = [];
data.genres.forEach(function (e) {
  if (genres.includes(e.id)) result.push(e.name);
});
console.log(result);

如果您想知道 forEach，这里有一个很好的参考：https://www.w3schools.com/jsref/jsref_foreach.asp

Answer 4

您可以使用 reduce 和 includes，正如其他人已经展示的那样。这将使代码更简洁一些，但不会改变整体运行时的复杂性。为了提高运行时的复杂性，您可能需要使用不同的数据结构。

例如

let genres = [1,2,3,4];

作为简单数组，您可以使用 Set，它具有更好的查找性能。

let genres = new Set([1,2,3,4]);

那么你可以这样使用

let result = data.genres
 .filter(g => genres.has(g.id))
 .map(g => g.name);

并且不需要任何显式 for 循环

Answer 5

当前时间复杂度为 O(MN)，其中 M 是 data.genres 的长度，N 是 genres 的长度。 JavaScript 中的时间复杂度取决于您使用的引擎，但在大多数情况下，您可以使用 Map 将此时间复杂度降低到 O(max{N,M}):

const getGenreName = () => {
  const dataGenresMap = new Map( // O(M)
    data.genres.map(({id,...params}) => [id,params]) // O(M)
  )
  let result = []
  for (let id of genres) { // O(N)
    if (dataGenresMap.has(id)) result.push(dataGenresMap.get(id).name) // O(1)
  }
  console.log(result)
}

Answer 6

如果你可能不止一次这样做，那么我建议使用 Map。通过创建哈希映射，检索每个 id 的流派名称的性能更高。

  let genres = [28, 12, 878];
  data = {
    genres: [
      {
        id: 28,
        name: 'Action',
      },
      {
        id: 12,
        name: 'Adventure',
      },
      {
        id: 16,
        name: 'Animation',
      },
      {
        id: 35,
        name: 'Comedy',
      },
      {
        id: 80,
        name: 'Crime',
      },
      {
        id: 99,
        name: 'Documentary',
      },
      {
        id: 18,
        name: 'Drama',
      },
      {
        id: 10751,
        name: 'Family',
      },
      {
        id: 14,
        name: 'Fantasy',
      },
      {
        id: 36,
        name: 'History',
      },
      {
        id: 27,
        name: 'Horror',
      },
      {
        id: 10402,
        name: 'Music',
      },
      {
        id: 9648,
        name: 'Mystery',
      },
      {
        id: 10749,
        name: 'Romance',
      },
      {
        id: 878,
        name: 'Science Fiction',
      },
      {
        id: 10770,
        name: 'TV Movie',
      },
      {
        id: 53,
        name: 'Thriller',
      },
      {
        id: 10752,
        name: 'War',
      },
      {
        id: 37,
        name: 'Western',
      },
    ],
  };
  
  const genreById = new Map ();
  data.genres.forEach(({id, name}) => genreById.set(id, name));
  
  const pushMapValueIfTruthy = map => array => key => {
    const val = map.get(key);
    if (val) {
      array.push(val);
    }
  };
  
  /** function that takes an array, then id, and pushes corresponding name (if exists) into the array. */
  const pushGenreNaneIfExists = pushMapValueIfTruthy(genreById);
  
  const getGenreNames = (ids) => {
    result = [];
    ids.forEach(pushGenreNaneIfExists(result));
    return result;
  };
  
  console.log(getGenreNames(genres));

如何提高这个片段的时间复杂度？

How to improve time complexity of this snippet?

javascript

arrays

object

big-o