Какова временная сложность сортировки сегментов O (n + k), если она использует сортировку вставками для сортировки каждого сегмента?

Question

Поскольку временная сложность сортировки вставки равна O (n ^ 2), какова средняя временная сложность сортировки сегмента O (n + k), поскольку она использует сортировку вставки в каждом сегменте?Здесь k - количество ведер.

Answer 1

Вы можете взглянуть на подробные расчеты средней сложности по времени.Хотя, здесь есть интуиция.

Во-первых, в худшем случае сортировка сегментов равна O (n ^ 2) .Это происходит всякий раз, когда все элементы оказываются в одном и том же сегменте.

Хотя сортировка сегментов основывается на равномерном распределении элементов по сегментам.Учитывая это предположение и учитывая количество сегментов, пропорциональных размеру входных данных, тогда средний сегмент должен содержать O (1) элементов.Другими словами, выбирая достаточное количество сегментов, вы сохраняете их размер небольшим.

Это означает, что сортировка сегментов незначительна для общей сложности времени.Выбор сортировки вставки становится разумным выбором, поскольку он имеет меньшие накладные расходы и не требует дополнительного места.