在研究数据结构的背景下初始化数组
我正在阅读CLRS对算法的介绍，在直接地址表一节下的书中有问题11.1练习4：
We wish to implement a dictionary by using direct addressing on a huge array. At
the start, the array entries may contain garbage, and **initializing** the entire array
is impractical because of its size. Describe a scheme for implementing a direct address
dictionary on a huge array. Each stored object should use O(1) space;
the operations SEARCH, INSERT, and DELETE should take O(1) time each; and
initializing the data structure should take O(1) time. (Hint: Use an additional array,
treated somewhat like a stack whose size is the number of keys actually stored in
the dictionary, to help determine whether a given entry in the huge array is valid or
not.)我理解解决方案只是创建另一个数组，并让它为存在的元素存储指向该数组的指针。
但在这种情况下，我对“初始化”的含义有点困惑。如果数组未被初始化，我们如何才能访问数据(即在Ai的第一个位置获取值)？
我也不知道为什么这个问题会说明这个内存约束。假设我们可以初始化数组，那么答案将如何变化？
回答 2
Stack Overflow用户
发布于 2020-08-29 16:33:36
问题是初始化一个长度为N的数组--将所有元素设置为一个已知值，如NULL --需要O(N)时间。
如果您有一个初始化为NULL的数组，那么实现一个直接访问表是非常容易的-- Ai == NULL意味着i没有值，如果i有一个值，那么它就存储在Ai中。
问题是如何避免O(N)初始化成本。如果数组没有初始化，那么所有Ai的初始值都可以是任何.那么，如何判断它是一个真正的值还是一个初始的垃圾呢？
解决方案不仅仅是创建另一个数组来存储指向原始数组的指针--您必须初始化另一个数组，然后又浪费了O(N)时间。
为了完全避免这一成本，你必须更聪明。
生成3个数组A、B和C，并将字典中的值总数计数为N。
那么，如果i的值是v：
- Ai = v;
- 0 <= Bi < N；
- C[Bi]= i
这样，B和C数组就可以跟踪A中哪些索引被设置为实际值，而无需初始化任何数组。添加新项时，需要检查条件(2)和(3)，以确定索引是否有效，如果没有，则需要：
- Ai =空
- Bi= N
- CN++ = i
这将索引i标记为有效，条件(2)和(3)将通过所有以后的检查。
由于所需的内存量，这一技术在实践中并不经常使用，但它确实意味着，在计算运行时复杂性时，理论上永远不必计算数组初始化的成本。
Stack Overflow用户
发布于 2020-08-28 21:57:55
在该上下文中，initializing意味着将数组中的值设置为存储类型的NULL、0或empty value。其思想是，当为数组分配内存时，所分配内存的内容是随机的，因此数组最终包含随机值。在这种情况下，initializing值意味着将它们设置为“空”值。
https://stackoverflow.com/questions/63641224
复制相似问题
腾讯云开发者
