Не знаете, какую сложность пространства использует мой объект карты в примере?

Question

Я учусь анализировать сложность пространства, но я запутался в анализе массива и объекта в JS. Так что я хотел бы получить помощь здесь.

ex1. массив []

int[] table = new int[26];
for (int i = 0; i < s.length(); i++) {
    table[s.charAt(i) - 'a']++;
}

ex1. взят из примера в сети и говорит, что сложность пространства равна O (1), потому что размер таблицы остается постоянным.

ex2. объект {}

let nums[0,1,2,3,4,5], map = {};
for (let i = 0; i < nums.length; i++) {
   map[ nums[i] ] = i;
}

Я думаю, ex2. использует O (n), потому что к объекту карты обращаются 6 раз. Однако, если я использую концепцию, извлеченную из ex1., Сложность пространства должна быть O (1)? Есть идеи, где я ошибся?

Answer 1

С точки зрения анализа сложности, в примере 1, сложность составляет O (1) , поскольку размер массива не увеличивается. Потому что вы инициализируете таблицу с фиксированным размером 26 (похоже, вы подсчитываете символы в строке?).

См. Приведенный ниже пример, который отслеживает количество алфавитов в строке (только маленькийбуквы для наглядности). В этом случае длина массива, который отслеживает количество алфавитов, никогда не изменится, даже если строка изменит свою длину.

function getCharacterCount(s){
    const array = new Int8Array(26);
    for (let i = 0; i < s.length; i++) {
        array[s.charCodeAt(i) - 97]++;
    }
    return array;
}

Теперь давайте вместо этого изменим реализацию на map. Здесь размер карты увеличивается по мере того, как в строке встречается новый символ. Так что

Теоретически, сложность пространства составляет O (n) .

Но на самом деле мы начали с карты длиной 0 (0 клавиш), и она не выходит за пределы 26. Если строка не содержит все символы, занимаемое пространство будет намного меньше, чеммассив, как в предыдущей реализации.

function getCharacterCountMap(s){
    const map = {};
    for (let i = 0; i < s.length; i++) {
        const charCode = s.charCodeAt(i) - 97;
        if(map[charCode]){
            map[charCode] = map[charCode] + 1
        }else{
            map[charCode] = 0;
        }
    }
    return map;
}

function getCharacterCount(s){
    const array = new Int8Array(26);
    for (let i = 0; i < s.length; i++) {
        array[s.charCodeAt(i) - 97]++;
    }
    return array;
}

function getCharacterCountMap(s){
    const map = {};
    for (let i = 0; i < s.length; i++) {
        const charCode = s.charCodeAt(i) - 97;
        if(map[charCode]){
            map[charCode] = map[charCode] + 1
        }else{
            map[charCode] = 1;
        }
    }
    return map;
}

console.log(getCharacterCount("abcdefabcedef"));
console.log(getCharacterCountMap("abcdefabcdef"));