javaScript 中的对象比较是线性时间还是常数时间？
Is object comparison in javaScript in linear or constant time?
我想知道，当 JavaScript 比较 2 个对象时，是否必须递归地遍历每个键以确定严格相等 (O(log(2n))？如果比较 [=15 中的字符串=]，是否必须按每个字母比较它们，或者二进制信息的总和是否足以进行 1 对 1 的比较 O(1)？比较 JSON 个对象更快，还是 javascript 个对象？
感谢任何部分的任何答案或对我的原始组合学的更正。
在 JS 中，对象通过引用进行比较（而不是 structural/deep 相等）。因为只比较固定长度的内存地址，所以比较复杂度为O(1)。
例如，即使 obj1 和 obj2 中的每个 key/value 对都相同，下面的代码片段总是打印错误。 obj1 和 obj2 不引用相同的底层对象，对象通过引用进行比较，而不是键和值。
let obj1 = { a: 1, b: 2 };
let obj2 = { a: 1, b: 2 };
console.log(obj1 == obj2 || obj1 === obj2); // => false
然而，此代码打印为真，因为在这种情况下 obj1 和 obj2 do 指的是同一个对象。
obj1 = { a: 1, b: 2 };
obj2 = obj1;
console.log(obj1 == obj2 && obj1 === obj2); // => true
如果您想比较两个对象的结构和内容，而不仅仅是评估引用相等性，您可以使用 Node 的 assert.deepEqual()，它与 key/value 对的总数呈线性关系比较。
要在浏览器中比较任意对象，您可以使用 JSON.stringify(obj1) === JSON.stringify(obj2)。这也与被比较的 key/value 对的数量大致呈线性关系，但它取决于 key/value 对的字符串化版本的长度，而不仅仅是 key/value 对的数量。你可以说它是 O(nm)，其中 n 是 k/v 对的数量，m 是对象中 k/v 对的平均字符串长度，这样 nm 就是字符串 JSON.stringify 产生。 （m 可能只是一个很小的常数，但在没有先验知识限制的情况下，它很可能会超过 n，因此您必须将其考虑在内）
一般来说，assert.deepEqual() 在最好的情况下可以更快，因为它可以 return 更早：只要被比较的 key/value 对不匹配，断言就可以失败并 return 早。如果前 k/v 对不匹配，assert.deepEqual() 可以在 O(1) 中 return。但是，最坏情况下，比较相等的对象，是O(n).
对于JSON.stringify，在比较开始之前必须将整个对象转换为字符串，因此最好和最坏的情况都是 O(nm)。您当然也可以实现自己的递归 deepEquals 方法来实现与 assert.deepEqual() 相同的性能，或者使用 lodash.isEqual()，它们不是原生的。
关于您的其他问题，字符串无法在 O(1) 中通过“它们的二进制信息之和”进行比较。两个不同的字符串可以求和为相同的值，并且确定该和仍然与二进制表示中的位数成线性关系。长度为 n 的字符串的二进制表示中的位数是 O(n)，因为每个字符都由固定位数表示。相反，如果您的意思是逐位比较字符串（这实际上是标准字符串比较中发生的事情），出于同样的原因，那仍然是 O(n)。
我认为您可能将固定大小整数的 O(1) 比较复杂度与字符串比较的复杂度混为一谈。相关的区别在于，当整数存储在内存的单个机器字中时，可以在 O(1) 中比较整数（例如，在 64 位机器上比较两个 <= 64 位整数），但字符串通常逐字符存储，整个字符串值可能不适合单个内存地址。在 JS 中唯一一次字符串比较总是 O(1) 是如果字符串之前是 interned，但这不会帮助你比较 JSON.stringified 对象，因为你仍然需要做前面的两个 O(nm) 字符串化。
我想知道，当 JavaScript 比较 2 个对象时，是否必须递归地遍历每个键以确定严格相等 (O(log(2n))？如果比较 [=15 中的字符串=]，是否必须按每个字母比较它们，或者二进制信息的总和是否足以进行 1 对 1 的比较 O(1)？比较 JSON 个对象更快，还是 javascript 个对象？
感谢任何部分的任何答案或对我的原始组合学的更正。
在 JS 中，对象通过引用进行比较（而不是 structural/deep 相等）。因为只比较固定长度的内存地址，所以比较复杂度为O(1)。
例如，即使 obj1 和 obj2 中的每个 key/value 对都相同，下面的代码片段总是打印错误。 obj1 和 obj2 不引用相同的底层对象，对象通过引用进行比较，而不是键和值。
let obj1 = { a: 1, b: 2 };
let obj2 = { a: 1, b: 2 };
console.log(obj1 == obj2 || obj1 === obj2); // => false
然而，此代码打印为真，因为在这种情况下 obj1 和 obj2 do 指的是同一个对象。
obj1 = { a: 1, b: 2 };
obj2 = obj1;
console.log(obj1 == obj2 && obj1 === obj2); // => true
如果您想比较两个对象的结构和内容，而不仅仅是评估引用相等性，您可以使用 Node 的 assert.deepEqual()，它与 key/value 对的总数呈线性关系比较。
要在浏览器中比较任意对象，您可以使用 JSON.stringify(obj1) === JSON.stringify(obj2)。这也与被比较的 key/value 对的数量大致呈线性关系，但它取决于 key/value 对的字符串化版本的长度，而不仅仅是 key/value 对的数量。你可以说它是 O(nm)，其中 n 是 k/v 对的数量，m 是对象中 k/v 对的平均字符串长度，这样 nm 就是字符串 JSON.stringify 产生。 （m 可能只是一个很小的常数，但在没有先验知识限制的情况下，它很可能会超过 n，因此您必须将其考虑在内）
一般来说，assert.deepEqual() 在最好的情况下可以更快，因为它可以 return 更早：只要被比较的 key/value 对不匹配，断言就可以失败并 return 早。如果前 k/v 对不匹配，assert.deepEqual() 可以在 O(1) 中 return。但是，最坏情况下，比较相等的对象，是O(n).
对于JSON.stringify，在比较开始之前必须将整个对象转换为字符串，因此最好和最坏的情况都是 O(nm)。您当然也可以实现自己的递归 deepEquals 方法来实现与 assert.deepEqual() 相同的性能，或者使用 lodash.isEqual()，它们不是原生的。
关于您的其他问题，字符串无法在 O(1) 中通过“它们的二进制信息之和”进行比较。两个不同的字符串可以求和为相同的值，并且确定该和仍然与二进制表示中的位数成线性关系。长度为 n 的字符串的二进制表示中的位数是 O(n)，因为每个字符都由固定位数表示。相反，如果您的意思是逐位比较字符串（这实际上是标准字符串比较中发生的事情），出于同样的原因，那仍然是 O(n)。
我认为您可能将固定大小整数的 O(1) 比较复杂度与字符串比较的复杂度混为一谈。相关的区别在于，当整数存储在内存的单个机器字中时，可以在 O(1) 中比较整数（例如，在 64 位机器上比较两个 <= 64 位整数），但字符串通常逐字符存储，整个字符串值可能不适合单个内存地址。在 JS 中唯一一次字符串比较总是 O(1) 是如果字符串之前是 interned，但这不会帮助你比较 JSON.stringified 对象，因为你仍然需要做前面的两个 O(nm) 字符串化。