这种专业化的复杂性是什么？

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).