algorithm - 这种特殊排序的复杂性是什么

Question

我想知道以下排序算法的复杂性(如 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 循环中增加了另一轮。但也许这对复杂性没有影响？

Answer 1

由于您已经有了伪代码，因此很容易找到复杂性。你有 2 个嵌套循环。外层总是运行 N-1 次，内层总是 |B|，其中 |B|是集合 B 的大小(桶数)。因此复杂度为 (N-1)*|B|这是 O(NB)。