Временная сложность операций над отсортированным массивом отсортированных списков

Question

У меня есть отсортированный массив из N элементов, равномерно распределенных по K спискам, который также отсортирован.Какова будет временная сложность (в кратчайшем обозначении Big-O) для:

1. Удаление наименьшего элемента.
2. Восстановление массива после удаления наименьшего элемента.
3. Удаление всех N элементов

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

Во второй части я не уверен (может быть O(NK)?)

Длятретья часть, это должно быть O(N), так как мы проходим весь массив, но, опять же, я не уверен

Answer 1

Конкретные примеры помогают.Допустим, у вас есть три списка (массива):

[7, 11, 15]
[3, 12, 19]
[2, 4, 6]

Для удаления наименьшего элемента необходимо сначала его найти.Отдельные списки расположены по порядку, а список списков - нет.Чтобы найти наименьший элемент, потребуется O (K), потому что вы должны выполнить последовательное сканирование списка списков.

После того, как вы нашли наименьший элемент, потребуется O (m) времени(где m - размер списка, который содержит наименьший элемент), чтобы удалить его.Причина в том, что когда вы удаляете первый элемент из списка, все остальные элементы должны двигаться вверх.То есть:

[2, 4, 6] становится [_, 4, 6], а затем вам нужно сдвинуть вещи, чтобы сделать [4, 6, _].(_ означает нулевое значение или любое другое значение, которое вы используете для обозначения «нет значения».)

Полагаю, вы могли бы сказать, что удаление - это O (1), а затем повторная сортировка массива равна O(m).

Вы можете удалить все элементы за O (N) времени, если вам все равно, в каком порядке вы их удалите.Если вы хотите удалить все элементы в отсортированном порядке, то сложность O (n * K), потому что каждый раз вам нужно найти самый маленький элемент.Вы можете улучшить это до O (n * log (K)), применив K-way merge, за счет O (K) дополнительной памяти.

Answer 2

Это зависит от того, что вы имеете в виду, когда говорите, что «K списки также сортируются».

Если числа распределены случайным образом по K спискам, но каждый из K списков отсортирован самтогда O (K) потребуется время, чтобы просмотреть заголовки всех списков, чтобы определить наименьший элемент.Однако, если числа разделены между K списками так, что K списков A, B, C, ... можно упорядочить так, чтобы A0 <= AN <= B0 <= BN <= C0 <= CN ... </em>, тогда требуется O (1) время, чтобы найти самый маленький элемент, потому что вы знаете, что он находится во главе первого списка.

Удаление наименьшего или наибольшего элемента массива сохраняет существующий отсортированный порядок, поэтому для этого требуется время O (1) .

Время, необходимое для «удаления» всех элементов, зависит отваша модель расчета.Это может занять O (1) время, если удаление считается просто удалением всей структуры данных.Однако, если каждый элемент требует отдельной очистки, тогда потребуется O (N + K) время: O (N) для стоимости доступа к каждому элементу и O (K) для стоимости доступа к каждому из списков.