Блог

Главная - Вопросы по программированию - Какова наилучшая сложность для проверки наличия слова анаграммы в списке?

Какова наилучшая сложность для проверки наличия слова анаграммы в списке?

#javascript #algorithm #performance #time-complexity #string-matching

#javascript #алгоритм #Производительность #сложность по времени #сопоставление строк

Вопрос:

Какой из этих двух алгоритмов имеет лучшую сложность, если мы рассмотрим O(n) , а не O(1) для sort , slice , join , split ? Я думаю, что второй вариант лучше с точки зрения производительности.

И знаете ли вы, можем ли мы записать его с лучшей сложностью или производительностью.

Это вопросы:

 Anagrams: 
a re-arrangement of letters that spells another word, 
for example: spot, tops, stop are anagrams. 

boolean containsAnagram(List<String> dictionary, String word)

assertTrue(containsAnagram(List.of("stop", "bus"), "pots"));
assertFalse(containsAnagram(List.of("stop", "bus"), "apple"));

И я написал свой код на javascript следующим образом:

 const containsAnagram = (dic, str) => {
      console.log(dic, str);
      for(let i=0; i< str.length; i  ){ 
          const letter = str[i];
          for(let j=0; j < dic.length ; j   ){
              const word = dic[j];
              for(let k=0; k < word.length ; k   ){
                  if(letter === word[k]){
                      dic[j] = word.slice(0, k)   word.slice(k 1, word.length);
                      // dic[j] is empty string and it is the end of the str , return true
                      if( dic[j] === '' amp;amp; str.length === i 1 ){
                          return true;
                      }
                      break;
                  }
              }
          }
      }
      return false;
    };
console.log(containsAnagram(["stop", "bus"], "pots"));
console.log(containsAnagram(["stop", "bus"], "apple"));

Что в основном задается O(n^3) , если учесть, что slice или substr есть o(1) . В то время как фактический случай таков, что slice или substr имеет сложность o(n) .

Итак, я переписываю его, используя функцию сортировки, следующим образом:

 const containsAnagram = (dic, str) => {
    console.log(dic, str);
    str = str.split('').sort().join(''); // n
    for(let j=0; j < dic.length ; j   ){
        const word = dic[j].split('').sort().join(''); // o (n*n*n*n)
        dic[j] = word ;
        if( word === str ){
            return true;
        }
    }
    return false;
};  
console.log(containsAnagram(["s", "s1"], "sp")); // false
console.log(containsAnagram(["s", "psso1"], "spos1"));  // true

Ответ №1:

Оба излишне сложны. .sort есть O(n log n) , нет O(n) , так что, хотя это улучшение, оно не так хорошо, как могло бы быть.

Чтобы уменьшить вычислительную сложность и перебирать каждый символ в dic и str ровно один раз, создайте функцию, которая превращает строку в объект, который подсчитывает количество вхождений каждого символа, а затем сравнивает значения объекта:

 const groupStr = str => {
  const obj = {};
  for (const char of str) {
    obj[char] = (obj[char] || 0)   1;
  }
  return obj;
};
const objsEqual = (obj1, obj2) => {
  const [keys1, keys2] = [obj1, obj2].map(Object.keys);
  if (keys1.length !== keys2.length) return false;
  return keys1.every(key1 => obj1[key1] === obj2[key1]);
};
const containsAnagram = (targets, input) => {
  const inputGrouped = groupStr(input);
  return targets.some(
    target => objsEqual(groupStr(target), inputGrouped)
  );
};

console.log(containsAnagram(["stop", "bus"], "pots"));
console.log(containsAnagram(["stop", "bus"], "apple"));

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

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

1. Интересно, что в основном этот алгоритм выдает O(n n n), подход аналогичен тому, что я сделал в первом решении, только вместо использования substring или slice . Вы используете словарь и считаете букву, которая устраняет проблему!

Метки: