Сложность следующего алгоритма поиска минимального значения в несортированном массиве

Используя подход «разделяй и властвуй», если мы многократно делим массив на две половины, пока они не уменьшатся до размера двух, после чего мы можем за время O (1) вернуть минимум из двух. Расширяя подход, чтобы объединить два подмассива A и B с их минимумом «a» и «b» соответственно, мы можем напрямую вернуть их минимум за время O (1), сделав шаг слияния операцией с постоянным временем.

По сути, это означает, что существует logN уровней, а сложность этапа слияния составляет O (1). Значит ли это, что сложность поиска минимального значения в несортированном массиве составляет O(logN) с использованием этого алгоритма?

Кроме того, обратитесь к этому обсуждению.

Поиск минимума в несортированном массиве за логарифмическое время


arrays algorithm time-complexity divide-and-conquer
person Ajax    schedule 02.11.2018    source источник
comment
Дерево рекурсии ветки в 2 раза. У вас будет экспоненциальное количество подмассивов.   -  person meowgoesthedog    schedule 02.11.2018

Ответы (3)


arrow_upward
1
arrow_downward

после чего мы можем за время O(1) вернуть минимум из двух.

Вы сравниваете пару значений за постоянное время, но у вас есть n/2 пар значений для сравнения. Это делает этот первый шаг всего O (n/2) (что уже O (n)), и суммирование каждого шага дает O (n/2 + n/4 + n/8 + ...).

Короче говоря, вам все еще нужно сделать как минимум n-1 сравнений. Вокруг этого нет никакой лазейки.

person Nelfeal    schedule 02.11.2018

arrow_upward
4
arrow_downward

Даже не глядя на ваш алгоритм, O(Log N) найти минимум навсегда невозможно.

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

Следовательно, поиск минимума является задачей Ω(N).

person Yves Daoust    schedule 02.11.2018

arrow_upward
0
arrow_downward

Хотя тот Нелфеал Ив Дауст ответил на него хорошо, я хочу добавить комментарий.

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

Практическое улучшение

Мы можем сделать это быстрее, если оставим больше операций и места в структуре данных.

  • Массив пуст

    • Insert(e) : Set minimum/maximum with the value of e. O(1)
    • Remove(e) : вернуть некоторое предопределенное значение. О(1)
    • Минимум/Максимум(e): вернуть некоторое предопределенное значение. О(1)

  • Массив не пуст

    • Insert(e) : Compare the value of e with the minimum/maximum. If the condition is met, then set minimum/maximum with the value of e. O(1)
    • Remove(e) : если mininum/maximum == e , то установить минимум/максимум как неизвестный (может быть NULL?). В противном случае просто удалите e из массива. О(1)
    • Минимум/максимум(e): если минимум/максимум неизвестен, найдите и установите минимум/максимум с помощью алгоритма O(N). Если минимум/максимум известен, просто верните его. О(N) или О(1).

За и против

Соотношение операций между Insert/Remove и Minimum/Maximum определяет производительность этого алгоритма. Если количество операций минимума/максимума больше, чем количество операций вставки/удаления, вероятностно, этот алгоритм работает быстрее по мере того, как массив становится все больше и больше.

person paganinist    schedule 03.11.2018