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

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){&nbsp; &nbsp; const array = new Int8Array(26);&nbsp; &nbsp; for (let i = 0; i < s.length; i++) {&nbsp; &nbsp; &nbsp; &nbsp; array[s.charCodeAt(i) - 97]++;&nbsp; &nbsp; }&nbsp; &nbsp; return array;}现在让我们将实现改为 map 。这里地图的大小随着字符串中遇到新字符而增加。所以从理论上讲，空间复杂度是 O(n)。但实际上，我们从长度为 0（0 个键）的 map 开始，它不会超过 26。如果字符串不包含所有字符，则占用的空间将比之前实现中的数组小得多。function getCharacterCountMap(s){&nbsp; &nbsp; const map = {};&nbsp; &nbsp; for (let i = 0; i < s.length; i++) {&nbsp; &nbsp; &nbsp; &nbsp; const charCode = s.charCodeAt(i) - 97;&nbsp; &nbsp; &nbsp; &nbsp; if(map[charCode]){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; map[charCode] = map[charCode] + 1&nbsp; &nbsp; &nbsp; &nbsp; }else{&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; map[charCode] = 0;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; return map;}function getCharacterCount(s){&nbsp; &nbsp; const array = new Int8Array(26);&nbsp; &nbsp; for (let i = 0; i < s.length; i++) {&nbsp; &nbsp; &nbsp; &nbsp; array[s.charCodeAt(i) - 97]++;&nbsp; &nbsp; }&nbsp; &nbsp; return array;}function getCharacterCountMap(s){&nbsp; &nbsp; const map = {};&nbsp; &nbsp; for (let i = 0; i < s.length; i++) {&nbsp; &nbsp; &nbsp; &nbsp; const charCode = s.charCodeAt(i) - 97;&nbsp; &nbsp; &nbsp; &nbsp; if(map[charCode]){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; map[charCode] = map[charCode] + 1&nbsp; &nbsp; &nbsp; &nbsp; }else{&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; map[charCode] = 1;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; return map;}console.log(getCharacterCount("abcdefabcedef"));console.log(getCharacterCountMap("abcdefabcdef"));