这个专用排序算法的复杂度是多少？

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循环中增加另一个循环。但也许这对复杂度没有影响？

- ADB

---

乍一看，我认为这是“O(NB)”（如果N == B，则可能为“O(N^2)”，如果N == 2B，则可能为“O(N^3)”等等...）。因为这个代码片段中B和N的大小似乎是固定的。 - FrustratedWithFormsDesigner

Answer 1

既然你已经有了伪代码，那么计算复杂度就很容易了。 你有两个嵌套循环。外层循环总是运行N-1次，内层总是运行|B|次，其中|B|是集合B的大小（桶的数量）。因此复杂度为(N-1)*|B|，即O(NB)。

- Tomer Vromen

Answer 2

您说得对，桶的数量确实会影响复杂度。只需看一下您的伪代码。在您要选择每个元素时，您必须搜索候选数组，其长度为B。因此，您执行的操作是O（B）N次复杂度。

- Maciej Hehl