javascript - Javascript 的引擎设计在更坏的情况下如何影响用户数据结构的实现？

Question

举个例子，一个使用哈希表实现关联数组（对象）的 JS Web 引擎。但正如我们所知，哈希表的情况更糟 O(n) 因为冲突是不可避免的。

假设我开始使用 Javascript 开发一种新的数据结构，这种数据结构如 LinkedList，插入/删除的情况更糟 O(1)。但是因为我用对象/数组来实现它。那么我的实现也至少是最坏的情况 O(n) 一定是真的。

我知道这个引擎优化得很好，一个好的哈希函数平均会产生 O(1)。但是，我只是想确认我的认识，这并不像教科书所说的那么简单。或者是吗？

我想在所有数据结构的根部都用数组实现，因为访问总是O（1），那么不应该用没有中间结构的数组来构建所有数据结构吗？此外，动态数组仍然有 delete O(n) 不能像我之前的例子一样会出现同样的问题吗？

这是使用低级编程语言的好处比使用高级语言更好的地方吗？这样的低层次没有那么多抽象，教科书的复杂性数字实际上可以匹配吗？

如果我的想法到处都是，请道歉。

标签： javascriptobjecttime-complexitycomputer-scienceimplementation

Answer 1

但是因为我用对象/数组实现了[我的自定义数据结构]。那么我的实现也至少是最坏的情况 O(n) 一定是真的。

不，您的链接列表不会在n任何地方使用带有键的对象。你会有一个

const linkedListNode = {
   value: …,
   next: null,
};

但即使这是使用具有O(n)最坏情况成员访问权限的 HashTable 实现的，在您的情况下也是如此n=2。您的对象中没有任意多个属性，只有两个。这就是你如何回到O(1).

这是使用低级编程语言的好处比使用高级语言更好的地方吗？这样的低层次没有那么多抽象，教科书的复杂性数字实际上可以匹配吗？

不会。即使在较低级别的编程语言中，您也可以开始质疑底层抽象。您认为在 C 中，内存中的索引数组访问是常数时间吗？不，因为页面错误和其他缓存恶作剧开始发挥作用。

这就是为什么教科书的复杂性总是根据机器模型来定义的。只要您将 JavaScript 执行模型中的对象属性访问定义为常量时间（这是一个非常合理的假设！它与现实世界非常相似），您的数字也确实适用于 JavaScript 代码。当然，您可以尝试解开抽象并根据较低级别的原语分析您的高级算法，但这样做没有意义。这正是我们首先拥有这些抽象的原因。