Оценка двух функций по их производительности

        //Function-A
        function duplicatesNumber(text) {
            var counts = {};
            let textLowered = text.toLowerCase();
            textLowered.split("").forEach(function (x) {
                counts[x] = (counts[x] || 0) + 1;
            });
            return Object.entries(counts).filter(arr => arr[1] > 1).length
        }

        //Function-B
        function duplicateCount(text) {
            return text.toLowerCase().split('').filter(function (val, i, arr) {
                return arr.indexOf(val) !== i && arr.lastIndexOf(val) === i;
            }).length;
        }
       
       //Function-B
         let start = performance.now();
        console.log(duplicateCount("aaBBcDDcefgheeaas"))
        let end = performance.now();
        console.log("Function-B: "+ (end-start));
     
         
        
         //Function-A
         let start1 = performance.now();
        console.log(duplicatesNumber("aaBBcDDcefgheeaas"))
        let end1 = performance.now();
        console.log("Function-A: "+ (end1-start1))
         

• У меня две функции, они обе делают одно и то же. Вернуть количество дубликатов.
• У меня вопрос об их выступлениях. Я только начал изучать структуры данных и алгоритмы в javascript. Я освещал Big O’Notation. Но, наверное, я не понял.
• Поскольку Function-A имеет для каждого метода, это означает, что это O (n). Разве это не значит, что Function-A должна быть медленнее, чем вторая? Как может быть функция A быстрее, чем функция B?

Сложность времени

• Стоимость функции А $ mathcal {O} left (n right) $
  • toLowerCase, split Стоимость $ mathcal {O} left (n right) $
  • forEach Стоимость $ mathcal {O} left (n right) $
  • Object.entries, filter Стоимость $ mathcal {O} left (n right) $
    • counts[x] чтение / запись может стоить $ mathcal {O} left (1 right) $ в среднем
• Стоимость функции B $ mathcal {O} left (n ^ 2 right) $
  • toLowerCase, split все еще стоит $ mathcal {O} left (n right) $
  • filter Стоимость $ mathcal {O} left (n ^ 2 right) $
    • indexOf, lastIndexOf Стоимость $ mathcal {O} left (n right) $
    • filter повторить вышеуказанную операцию $ mathcal {O} left (n right) $ раз, таким образом $ mathcal {O} left (n cdot n right) $

Потребление времени чаще всего происходило в циклах. Не только forEach, fliter, но также toLowerCase, split, indexOf петли. Вы неправильно подсчитали производительность вложенных циклов.

Также обратите внимание, что нотация большого О предназначена для описания того, насколько быстро увеличивается потребляемое время при увеличении размера ввода. Это не обязательно означает, что алгоритм с лучшей нотацией большого O всегда будет быстрее.

Реализация

• Не используйте str.split(''), используйте [...str] если вы можете. Разделенный не будет правильно обрабатывать некоторые точки Unicode. Например, [...'𰻝𰻝面'].length 3, но '𰻝𰻝面'.split('').length 5.
• Использовать Map если можете (нет необходимости поддерживать старые браузеры). Object не идеальный способ использовать в качестве словаря. Только если вы хотите сохранить поддержку ES5, вы можете использовать Object.create(null) вместо.
• Вы можете подсчитать, сколько записей имеет не менее 2 во время итерации, отслеживая, если count[x] == 2 после увеличения. Таким образом, нет необходимости повторять Object.entries позже.