不确定我的地图对象在示例中使用的空间复杂度是多少？

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

从复杂度分析的角度来看，在ex 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 个键）的 map 开始，它不会超过 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"));