Какова сложность наихудшего случая для нахождения n / 2 наименьших значений для разных структур данных?

Question

Для различных структур данных, таких как связанные списки, массивы (отсортированные / несортированные, деревья и т. Д. Размера n), какова сложность времени наихудшего случая нахождения n / 2 наименьших значений в каждом из них?так же, как сложность для операций поиска?

Редактировать: Итак, какова сложность для этих структур данных? Несортированный связанный список, несортированный массив, Splay Tree и хеш-таблицы?

Answer 1

Это полностью зависит, например, от структуры данных и от того, отсортированы они или нет.

Если вы рассматриваете сбалансированное дерево, то найти n / 2 наименьших значений будет ... "все значения«слева» от корня.

Вы не можете обобщить его так сильно, это полностью зависит от структуры данных.

Answer 2

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

Объедините это с алгоритмом, таким как BogoSort , и вы можете получить довольно впечатляющие (из-за отсутствия лучшего слова) цифры сложности наихудшего случая ...

Answer 3

Не обязательно. Например, для отсортированного массива вы можете найти n / 2 наименьших значений за постоянное время.