Dav*_*ave 13 language-agnostic algorithm data-structures
A是一个从整数1到n随机顺序的数组.
我需要在至少日志时间内随机访问i第一个元素的第一个最大元素j.
到目前为止我所提出的是一个n x n矩阵M,其中(i, j)位置中的元素是i第一个中最大的元素j.这给了我恒定的随机访问,但需要n^2存储.
按构造,M按行和列排序.此外,每列与其邻居的区别在于单个值.
任何人都可以提出一个方法来压缩M到n log(n)空间或更好,具有log(n)或更好的随机存取时间？
rob*_*off 10
我相信你可以在O(log(N))时间内执行访问,给定O(N log(N))预处理时间和O(N log(N))额外空间.这是如何做.
您可以扩充红黑树以支持在O(log(N))时间内select(i)检索排名元素的操作i.例如,请参阅此PDF或" 算法简介"的相应章节.
您可以select(i)以功能方式实现红黑树(甚至一个增强以支持),以便插入操作返回一个新树,该树与旧树共享除O(log(N))节点之外的所有节点.例如,参见Chris Okasaki的Purely Functional Data Structures.
我们将构建一个T纯函数增强红黑树的数组,以便树T[j]存储从最大到最小排序0 ... j-1的第一个j元素的索引A.
基本情况:T[0]创建一个只有一个节点的增强红黑树,其数据为数字0,它是数组前1个元素中第0个最大元素的索引A.
感应步骤:对于每一个j从1到N-1,在T[j]通过纯粹的功能上插入具有索引的新节点创建增强的红黑树j到树T[j-1].这最多创建了O(log(j))个新节点; 其余节点共享T[j-1].这需要O(log(j))时间.
构造阵列的总时间T是O(N log(N)),并且使用的总空间也是O(N log(N)).
一旦T[j-1]被创建,您可以访问i第一届最大元素j的元素A通过执行T[j-1].select(i).这需要O(log(j))时间.请注意,您可以T[j-1]在第一次需要时懒惰地创建.如果A非常大并且j总是相对较小,这将节省大量的时间和空间.