Блог

Главная - Вопросы по программированию - Какова большая ошибка нового набора (arr1)?

Какова большая ошибка нового набора (arr1)?

#javascript #arrays #set #big-o

#javascript #массивы #набор #big-o

Вопрос:

Я решал небольшую задачу по поиску общих элементов в двух массивах

 function isCommonElementsPresent2(arr1,arr2){
   let set = new Set();

   for(let i=0;i<arr1.length;i  ){
      set.add(arr1[i]);
   }

   for(let i=0;i<arr2.length;i  ){
     if(set.has(arr2[i])){
       console.log(arr2[i]);
     }
   }
}  //Big Oh of this is O(N M)

Теперь, если я решу ту же проблему, что и ниже

Чем станет Big-Oh? Это будет то же самое или изменится? Что такое Big-Oh нового набора (arr1)? let set = new Set(arr1); 

 function isCommonElementsPresent2(arr1,arr2){
   let set = new Set(arr1);

   for(let i=0;i<arr2.length;i  ){
     if(set.has(arr2[i])){
       console.log(arr2[i]);
     }
   }
}
isCommonElementsPresent2(["a","b","y","e","f"],["z","y","f"]);

//What is the Big-Oh of this code block?

Может ли кто-нибудь помочь мне здесь?

Комментарии:

1. Это должно быть то же самое. new Set(arr) должен содержать цикл, подобный вашему.

2. В обоих случаях он линейный в среднем и квадратичный в худшем случае.

3. @MoB. Нет, Set s имеют гарантированное сублинейное время доступа, поэтому оно никогда не будет квадратичным

4. @Bergi Для среднего / амортизированного случая гарантируется сублинейное время доступа. Обычные реализации полагаются на хеширование, поэтому сложность в наихудшем случае действительно квадратична: а именно в маловероятном случае, когда всегда возникают коллизии хэшей.

Ответ №1:

Вычислительная сложность такая же. В обоих случаях каждый элемент arr1 должен быть повторен, чтобы быть помещенным в набор.

 let set = new Set();
for(let i=0;i<arr1.length;i  ){
  set.add(arr1[i]);
}

аналогично дорого

 let set = new Set(arr1);