这种特殊排序的复杂性是多少
我想知道以下排序算法的复杂性（如 O(...) ）：
- 有 B 个桶
- ，总共包含 N 个元素，分布在桶中不均匀。
- 每个桶中的元素都已排序。
排序将每个桶中的所有元素组合到一个排序列表中：
- 使用大小为 B 的数组存储每个桶的最后排序元素（从 0 开始）
- 检查每个桶（在最后存储的索引处）并找到最小元素
- 复制最终排序数组中的元素，增加数组计数器，
- 增加我们从中选择的桶的最后一个排序元素，
- 执行这些步骤 N 次
或以伪代码：
for i from 0 to N
smallest = MAX_ELEMENT
foreach b in B
if bIndex[b] < b.length && b[bIndex[b]] < smallest
smallest_barrel = b
smallest = b[bIndex[b]]
result[i] = smallest
bIndex[smallest_barrel] += 1
我认为复杂度是 O(n)，但问题是我发现复杂性的一个问题是，如果 B 增长，它比 N 增长的影响更大，因为它在 B 循环中增加了另一轮。但这也许对复杂性没有影响？
I would like to know the complexity (as in O(...) ) of the following sorting algorithm:
- There are B barrels
- that contain a total of N elements, spread unevenly across the barrels.
- The elements in each barrel are already sorted.
The sort combines all the elements from each barrel in a single sorted list:
- using an array of size B to store the last sorted element of each barrel (starting at 0)
- check each barrel (at the last stored index) and find the smallest element
- copy the element in the final sorted array, increment the array counter
- increment the last sorted element for the barrel we picked from
- perform those steps N times
or in pseudo code:
for i from 0 to N
smallest = MAX_ELEMENT
foreach b in B
if bIndex[b] < b.length && b[bIndex[b]] < smallest
smallest_barrel = b
smallest = b[bIndex[b]]
result[i] = smallest
bIndex[smallest_barrel] += 1
I thought that the complexity would be O(n), but the problem I have with finding the complexity is that if B grows, it has a larger impact than if N grows because it adds another round in the B loop. But maybe that has no effect on the complexity?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
由于您已经有了伪代码，因此很容易找到复杂性。
你有 2 个嵌套循环。外部始终运行 N-1 次，内部始终运行 |B|，其中 |B|是集合 B 的大小（桶数）。因此复杂度为 (N-1)*|B|即 O(NB)。
Since you already have pseudo-code, finding the complexity is easy.
You have 2 nested loops. The outer one always runs N-1 times, the inner always |B|, where |B| is the size of the set B (number of barrels). Therefore the complexity is (N-1)*|B| which is O(NB).
你是对的，桶的数量改变了复杂性。只要看看你的伪代码。对于您要选择的每个元素，您必须搜索候选数组，其长度为 B。因此您将执行复杂度为 O(B) N 次的操作
You are correct that the number of barrels changes the complexity. Just look at Your pseudocode. For every element You are about to pick, You have to search the array of candidates, the length of which is B. So You are performing an operation of complexity O(B) N times