试图理解动态二进制搜索问题
Trying to understand dynamic binary search question
Introduction to Algorithms 有以下问题
Binary search of a sorted array takes logarithmic search time, but the
time to insert a new element is linear in the size of the array. We
can improve the time for insertion by keeping several sorted arrays.
Specifically, suppose that we wish to support SEARCH and INSERT on a
set of n elements. Let k equal the ceiling of lg(n + 1) , and let the
binary representation of n be (nk-1, nk-2 ... n0). We have k sorted
arrays (A0, A1, Ak-1) where for i = (0, 1, ... k-1), the length of
array Ai is 2i. Each array is either full or empty, depending on
whether ni = 1 or ni = 0, respectively. The total number of elements
held in all k arrays is therefore the sum of ni * 2i from 0 to k-1
which equals n. Although each individual array is sorted, elements in
different arrays bear no particular relationship to each other.
我很难理解它描述的数据结构。具体来说，我对行 " 感到困惑，并让 n 的二进制表示为 (nk-1, nk-2 ... n0)" 我明白二进制表示是什么，但是，我对 "(nk-1, nk-2 ... n0)”。 n不是已经定义了吗？ n 是否有 k-1 个变体？还是 n 受 k 的限制？我们只是在看二进制的 k-1 位吗？
这行是什么意思？
还有它与有什么关系"每个数组是满的还是空的，取决于ni = 1或ni = 0"?
例如，如果我有数组 A = {0, 1, 2, 3, 4, 5, 6}
我知道 k = 3，因此我有 3 个数组 A0、A1、A2 长度为 1, 2, 4. 但是
我不明白这些数组的内容是什么。
数组 A0、A1、A2 的内容是什么是？
n项在全数组中任意分布。唯一的限制是数组 i 中的项目数，如果它已满，则为 2i.
我确定（或者至少我希望！）您没有粘贴很多文本，尽管您引用的文本足以弄清楚发生了什么。
您必须考虑在添加项目时 n 的二进制表示会发生什么。
假设您有 11 件商品，那么 n=11。 11的二进制表示是1011，所以A0，A1，A3 是满的，A2 是空的。每个完整数组中的项数等于其二进制位值，因此项总数为 11.
现在当我们插入一个项目时，n 将变为 12。二进制表示现在是 1100。 A0和A1因此被清空，A2被填满，当然，我们清空出来的元素A0和A1，还有新的item.
每次插入时，可能有一些满数组必须清空，还有一个空数组必须用它们的项和新的数组按排序顺序填充。这需要的时间与移动的项目数量成正比。
插入的摊销成本对于每个数组都是常数，因此插入的总摊销成本为 O(log N)。
搜索的成本是O(log2 N)，因为你必须搜索所有的全数组。
Introduction to Algorithms 有以下问题
Binary search of a sorted array takes logarithmic search time, but the time to insert a new element is linear in the size of the array. We can improve the time for insertion by keeping several sorted arrays.
Specifically, suppose that we wish to support SEARCH and INSERT on a set of n elements. Let k equal the ceiling of lg(n + 1) , and let the binary representation of n be (nk-1, nk-2 ... n0). We have k sorted arrays (A0, A1, Ak-1) where for i = (0, 1, ... k-1), the length of array Ai is 2i. Each array is either full or empty, depending on whether ni = 1 or ni = 0, respectively. The total number of elements held in all k arrays is therefore the sum of ni * 2i from 0 to k-1 which equals n. Although each individual array is sorted, elements in different arrays bear no particular relationship to each other.
我很难理解它描述的数据结构。具体来说，我对行 " 感到困惑，并让 n 的二进制表示为 (nk-1, nk-2 ... n0)" 我明白二进制表示是什么，但是，我对 "(nk-1, nk-2 ... n0)”。 n不是已经定义了吗？ n 是否有 k-1 个变体？还是 n 受 k 的限制？我们只是在看二进制的 k-1 位吗？
这行是什么意思？
还有它与有什么关系"每个数组是满的还是空的，取决于ni = 1或ni = 0"?
例如，如果我有数组 A = {0, 1, 2, 3, 4, 5, 6}
我知道 k = 3，因此我有 3 个数组 A0、A1、A2 长度为 1, 2, 4. 但是 我不明白这些数组的内容是什么。
数组 A0、A1、A2 的内容是什么是？
n项在全数组中任意分布。唯一的限制是数组 i 中的项目数，如果它已满，则为 2i.
我确定（或者至少我希望！）您没有粘贴很多文本，尽管您引用的文本足以弄清楚发生了什么。
您必须考虑在添加项目时 n 的二进制表示会发生什么。
假设您有 11 件商品，那么 n=11。 11的二进制表示是1011，所以A0，A1，A3 是满的，A2 是空的。每个完整数组中的项数等于其二进制位值，因此项总数为 11.
现在当我们插入一个项目时，n 将变为 12。二进制表示现在是 1100。 A0和A1因此被清空，A2被填满，当然，我们清空出来的元素A0和A1，还有新的item.
每次插入时，可能有一些满数组必须清空，还有一个空数组必须用它们的项和新的数组按排序顺序填充。这需要的时间与移动的项目数量成正比。
插入的摊销成本对于每个数组都是常数，因此插入的总摊销成本为 O(log N)。
搜索的成本是O(log2 N)，因为你必须搜索所有的全数组。