java - 数据结构可以在不使用任何数组的情况下拥有 O(1) 访问时间吗？

Question

我正在参加 CS 入门类(class)，第一个项目有以下限制:

You may NOT:

• Make your program part of a package.
• Add additional public methods or variables.
• Use any built in Java Collections Framework classes anywhere in your program (e.g. no ArrayList, LinkedList, HashSet, etc.).
• Use any arrays anywhere in your program.
• Add any additional import statements (or use the “fully qualified name” to get around adding import statements).

看到该项目的限制让我想知道在这些限制内人们实际上还可以做哪些其他事情。我看到的主要限制是“无数组”子句。

是否可以设计一个受这些约束影响的数据结构来模拟数组的性能特征？具体来说，数据结构应该表示一个固定长度的序列，支持通过索引“获取”或“设置”的操作，并且这些操作应该花费O(1)的时间，与序列的长度无关。

虽然可以构建类似图的结构，例如链表和树，但对这些数据结构的“获取”和“设置”操作将分别花费 O(n) 或 O(log n) 时间。我能想到的唯一的另一件事是一个具有几千个私有(private)字段和一个通过索引“获取”或“设置”的 switch 语句的类，但这仅适用于固定的序列长度。

Answer 1

我认为，如果您遵循规则的精神，那么您显然无法比 O(log n) 时间更好地获取或设置元素。原因是您实例化的每个对象最多可以存储固定数量的数据项和对其他对象的固定数量的引用，由该对象拥有的字段数量定义。

设 D 为对象保存的数据项的(最大)数量，F 为对象保存的引用字段的(最大)数量。需要明确的是，D 计算用于存储实际“数组”数据的字段，F 计算用于数据结构本身的字段。

如果您的访问时间为 O(1)，那么您最多可以遵循 O(1) 次引用来访问单元格，这意味着您的“数组”大小仅限于 O(D * F^R)，其中 R 是对完成一项操作所允许遵循的引用数量的固定限制。如果 D、F 和 R 三个都恒定，那么“数组”的大小也是恒定的。因此，在给定的限制下，模拟任意大小的数组数据结构的性能特征是不可能的。

这个论点可以进一步扩展，以证明 R 必须至少为 O(log n) 才能达到 n 个不同的数据项；即您必须遵循至少 O(log n) 次引用才能访问某个项目。您可以使用完全二叉树来实际实现此限制。

<小时/>

也就是说，至少有一种方法可以遵循规则的文字而不遵循规则的精神。

严格禁止您使用数组或 JCF 库类，但关于第三方库类的唯一规则是不允许您导入它们或通过完全限定名称引用它们。您可以使用 ClassLoader.loadClass方法从第三方库加载集合类，通过反射实例化它，将其赋值给Object类型的变量，然后通过反射调用其方法。从技术上讲，这是允许的，因为 loadClass 采用“二进制名称”，而不是要加载的类的“完全限定名称”。 (我将让律师来争论您是否需要加载一个二进制名称​​不是完全限定名称的类。)

对于学究来说:我将有关数组的规则解释为您的代码中不能有数组(大概除了 main 方法中的 String[] args )，而不是您的代码调用的其他人的代码中没有数组；否则例如您的程序被禁止打印任何输出，因为写入 System.out 的数据会缓冲在数组中。我认为该规则不太可能旨在禁止打印任何输出。