长数组所有旋转的内存和时间高效排序
Memory and time-efficient sorting of all rotations of a long array
我正在寻找一种内存和时间高效的解决方案来解决以下问题。很容易想到一个使用 O(n2) 内存和 O(n2 log n) 时间的基本算法（？），我想知道是否有一种算法可以显着提高内存和时间效率（对于某些输入结构）。
输入：长度为 n 的数组 a 填充了非负整数。数组中的每个整数的大小都小于或等于 b。我对 n 很大（数千万）而 b 与 n（数百）相比相对较小的设置感兴趣。我们可以假设 a 中任何特定整数的出现次数以 m 为界，其中 m 的数量级为 n/b.
考虑数组a所有旋转的集合，即如果a = (a1, a2, .. ., an), 那么它的旋转是(a1, a2, ... , an), (a2, a3, ..., an, a1), (a3, a4, ..., an, a1, a2), ..., (a n, a1, a2, ..., an- 1).设 r1, r2, ..., rn 表示字典序排序（递增）数组 a 的旋转顺序（使用 0 < 1 < 2 < ... < b）。
Output：两个数组first和last，分别存储第一个和最后一个元素r1, r2, ..., rn 按照排序顺序.
基本算法（不是内存或时间效率）：构造a的所有旋转并将它们存储在矩阵A中（使用O（n 2 ) 内存）。定义一个排序例程（使用标准排序技术）对 A 进行排序。提取已排序矩阵的第一列和最后一列。大概排序步骤的最佳时间复杂度是 O(n2 log n)，即排序算法的 O(n log n) 乘以每个成对比较的 O(n) .
第二种算法：我们可以遍历数组并存储其中以任何小于或等于 b 的整数 i 开头的位置（这是一个 O(n)时间和 O(nm) 内存操作）。然后，我们可以生成所有以特定整数 i 开头的旋转，并根据基本算法对这个旋转矩阵进行排序（存储这个矩阵使用 O(nm) 内存，排序大概需要 O(mn log m) 时间）。通过对从 0 到 b 的每个整数 i 重复该过程，很容易构造输出。
是否有使用定制排序策略的内存效率更高的方法？我很有希望，因为存储输出只需要 O(n) 内存。
让我们构造一个更好的算法来找到第一个旋转。构建字典序最后一个也是同样的问题，只是倒序排序。我们需要跟踪的只是最小旋转是多少，以及我们目前可能处于什么位置。这是 Python 这个想法。
def min_rotation (elements):
rotation = []
positions = [i for i in range(len(elements))]
while len(rotation) < len(elements):
min_element = elements[positions[0]]
new_positions = []
for i in range(len(positions)):
# Get the position and start rotating.
position = positions[i]
if elements[position] < min_element:
min_element = elements[position]
elif min_element <elements[position]:
continue
new_position = (position + 1) % len(elements)
new_positions.append(new_position)
positions = new_positions
rotation.append(min_element)
return rotation
最坏的情况是 O(n) 内存和 O(n*n) 运行 时间。您将在常量数组上命中它。
预期的情况会是O(n) 运行次，因为positions的数量迅速向1移动。
在 O(nlogn) 中为给定数组计算 suffix array。请注意，链接实现对循环移位进行排序（特殊字符用于后缀 - 你不需要它） - 正是你需要的（但 "sorts" 没有物理排序）
然后从后缀数组中提取由索引寻址的初始数组元素 - 这是需要的起始元素列表（结束元素位于之前的索引处）。
P[0] 包含最小循环移位的位置，因此 A[P[0]] 和 A[P[0]-1] 是第一对， P[1] - 下一个最小移位的位置等等
我正在寻找一种内存和时间高效的解决方案来解决以下问题。很容易想到一个使用 O(n2) 内存和 O(n2 log n) 时间的基本算法（？），我想知道是否有一种算法可以显着提高内存和时间效率（对于某些输入结构）。
输入：长度为 n 的数组 a 填充了非负整数。数组中的每个整数的大小都小于或等于 b。我对 n 很大（数千万）而 b 与 n（数百）相比相对较小的设置感兴趣。我们可以假设 a 中任何特定整数的出现次数以 m 为界，其中 m 的数量级为 n/b.
考虑数组a所有旋转的集合，即如果a = (a1, a2, .. ., an), 那么它的旋转是(a1, a2, ... , an), (a2, a3, ..., an, a1), (a3, a4, ..., an, a1, a2), ..., (a n, a1, a2, ..., an- 1).设 r1, r2, ..., rn 表示字典序排序（递增）数组 a 的旋转顺序（使用 0 < 1 < 2 < ... < b）。
Output：两个数组first和last，分别存储第一个和最后一个元素r1, r2, ..., rn 按照排序顺序.
基本算法（不是内存或时间效率）：构造a的所有旋转并将它们存储在矩阵A中（使用O（n 2 ) 内存）。定义一个排序例程（使用标准排序技术）对 A 进行排序。提取已排序矩阵的第一列和最后一列。大概排序步骤的最佳时间复杂度是 O(n2 log n)，即排序算法的 O(n log n) 乘以每个成对比较的 O(n) .
第二种算法：我们可以遍历数组并存储其中以任何小于或等于 b 的整数 i 开头的位置（这是一个 O(n)时间和 O(nm) 内存操作）。然后，我们可以生成所有以特定整数 i 开头的旋转，并根据基本算法对这个旋转矩阵进行排序（存储这个矩阵使用 O(nm) 内存，排序大概需要 O(mn log m) 时间）。通过对从 0 到 b 的每个整数 i 重复该过程，很容易构造输出。
是否有使用定制排序策略的内存效率更高的方法？我很有希望，因为存储输出只需要 O(n) 内存。
让我们构造一个更好的算法来找到第一个旋转。构建字典序最后一个也是同样的问题，只是倒序排序。我们需要跟踪的只是最小旋转是多少，以及我们目前可能处于什么位置。这是 Python 这个想法。
def min_rotation (elements):
rotation = []
positions = [i for i in range(len(elements))]
while len(rotation) < len(elements):
min_element = elements[positions[0]]
new_positions = []
for i in range(len(positions)):
# Get the position and start rotating.
position = positions[i]
if elements[position] < min_element:
min_element = elements[position]
elif min_element <elements[position]:
continue
new_position = (position + 1) % len(elements)
new_positions.append(new_position)
positions = new_positions
rotation.append(min_element)
return rotation
最坏的情况是 O(n) 内存和 O(n*n) 运行 时间。您将在常量数组上命中它。
预期的情况会是O(n) 运行次，因为positions的数量迅速向1移动。
在 O(nlogn) 中为给定数组计算 suffix array。请注意，链接实现对循环移位进行排序（特殊字符用于后缀 - 你不需要它） - 正是你需要的（但 "sorts" 没有物理排序）
然后从后缀数组中提取由索引寻址的初始数组元素 - 这是需要的起始元素列表（结束元素位于之前的索引处）。
P[0] 包含最小循环移位的位置，因此 A[P[0]] 和 A[P[0]-1] 是第一对， P[1] - 下一个最小移位的位置等等