Временная сложность для функции анаграммы JavaScript

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

function anagramDelete(str1, str2){
    let obj1 = {}, obj2 = {};

    // Load obj1 with all characters of str1 and their count
    str1.split('').forEach((char)=> {
        if(char in obj1){
            obj1[char]++;
        } else {
            obj1[char] = 1;
        }
    });

    // Load obj2 with all characters of str1 and their count
    str2.split('').forEach((char)=> {
        if(char in obj2){
            obj2[char]++;
        } else {
            obj2[char] = 1;
        }
    });

    // Track # of chars deleted
    let numOfDeletions = 0;

    // Compare each char in obj1 w obj2 and count deletions
    for(char in obj1){
        if(obj2[char]){
            numOfDeletions += Math.abs(obj2[char] - obj1[char]);
        } else {
            numOfDeletions += obj1[char];
        }
    }
    // Compare each char in obj2 w obj1 and count deletions
    for(char in obj2){
        if(!obj1[char]){
            numOfDeletions += obj2[char];
        }
    }
    return numOfDeletions;
}

Насколько я могу судить, поскольку циклов 4, это будет O (4n) или просто O (n). Я говорю это, потому что нет вложенных циклов. Это правильно? Любые лучшие решения?


javascript computer-science time-complexity anagram
person DGwang    schedule 04.01.2018    source источник
comment
Я бы все равно сказал, что это O(n). Потому что 4 цикла for не делают его в 4 раза медленнее.   -  person Jonas Wilms    schedule 04.01.2018

Ответы (3)


arrow_upward
1
arrow_downward

Вы можете использовать один объект и суммировать только абсолютные значения.

Это решение использует строки как массивы, подобные объектам.

function anagramDelete(str1, str2) {
    var letters = {};

    Array.prototype.forEach.call(str1, char => letters[char] = (letters[char] || 0) + 1);
    Array.prototype.forEach.call(str2, char => letters[char] = (letters[char] || 0) - 1);
 
    return Object.keys(letters).reduce((r, k) => r + Math.abs(letters[k]), 0);
}

console.log(anagramDelete('anagram', 'function'));

person Nina Scholz    schedule 04.01.2018

arrow_upward
0
arrow_downward

Ваш код O(n + m); в общем, не слишком заботятся о константах в классе сложности. n — это длина первой строки, а m — длина второй строки.

Кроме того: если быть точным в вашем случае, поскольку вы упомянули O(4n), я не уверен, что это правильно. Вы дважды используете функцию split, которая в вашем случае превращает строку в массив символов. Вы не учли это в своем анализе.

O(n + m) будет правильным ответом.

И если вы хотите детализировать анализ, это будет O(3n + 3m). Это потому, что:
- для первой строки вы используете split (O(n)), вы перебираете каждый символ (O(n)) и снова выполняете цикл для сравнения (O(n))
- для второй строки вы используете split ( O(m)), вы перебираете каждый символ (O(m)) и снова выполняете цикл для сравнения (O(m))

Я предполагаю, что ваш код правильный. Я не проверял это.

PS:
Если вы заинтересованы в точной настройке констант, вы можете обратиться к другим ответам, они, вероятно, быстрее, чем ваш код в теории. На практике я не думаю, что это имеет большое значение.

person Ely    schedule 04.01.2018

arrow_upward
0
arrow_downward

Не лучше, а короче:

  function anagramDelete(str1, str2){
   const chars = {};
   var result = 0;

   for(const char of str1)
     chars[char] = (chars[char] || 0) +1;

   for(const char of str2)
     chars[char] = (chars[char] || 0) -1;

   for(const [char, count] of Object.entries(chars))
    result += Math.abs(count);

   return result;
 }
person Jonas Wilms    schedule 04.01.2018
comment
Что, если chars[char] - 1 == 0 вместо этого станет -1. - person James; 05.01.2018