Какова сложность этого специализированного вида

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

Answer 2

Вы правы, что количество бочек меняет сложность. Просто посмотрите на свой псевдокод. Для каждого элемента, который вы собираетесь выбрать, вы должны найти массив кандидатов, длина которого равна B. Итак, вы выполняете сложную операцию O (B) N раз