javaScript 中的对象比较是线性时间还是恒定时间？

在 JS 中，对象通过引用进行比较（而不是结构/深度相等）。因为只比较一个固定长度的内存地址，所以比较是 O（1）。

例如，下面的代码片段始终打印 false，即使 和 上的每个键/值对都相同。 并且不引用相同的基础对象，并且对象是通过引用而不是键和值来比较的。obj1obj2obj1obj2

let obj1 = { a: 1, b: 2 };
let obj2 = { a: 1, b: 2 };
console.log(obj1 == obj2 || obj1 === obj2); // => false

但是，此代码打印 true，因为在本例中，and do 引用同一对象。obj1obj2

obj1 = { a: 1, b: 2 };
obj2 = obj1;
console.log(obj1 == obj2 && obj1 === obj2); // => true

如果要比较两个对象的结构和内容，而不仅仅是评估引用相等性，则可以使用 Node 的 ，它在要比较的键/值对总数中是线性的。assert.deepEqual()

要比较浏览器中的任意对象，可以使用 .在比较的键/值对数量方面，这也大致呈线性关系，但它取决于键/值对的字符串化版本的长度，而不仅仅是键/值对的数量。你可以说它是 O（nm），其中 n 是 k/v 对的数量，m 是对象中 k/v 对的平均字符串长度，因此 nm 是 JSON.stringify 生成的字符串的总长度。（m 可能只是一个很小的常数，但如果没有先验知识限制它，它很可能超过 n，所以你必须把它考虑在内）JSON.stringify(obj1) === JSON.stringify(obj2)

一般来说，assert.deepEqual（） 在最好的情况下会更快，因为它可以更早地返回：一旦被比较的键/值对不匹配，断言就会失败并提前返回。如果第一个 k/v 对不匹配，assert.deepEqual（） 可以在 O（1） 中返回。然而，在最坏的情况下，比较相等的对象，它是 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），如果字符串之前被隔离过，但这无助于比较 JSON.stringified 对象，因为您仍然需要预先执行两个 O（nm） 字符串化。