Сложность следующего алгоритма, чтобы найти минимальное значение в несортированном массиве

Question

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

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

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

Нахождение минимума в несортированном массиве за логарифмическое время

Answer 1

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

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

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

Answer 2

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

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

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

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

• Массив пуст

  • Вставить (e): установить минимальное / максимальное значения e. O (1)
  • Remove (e): вернуть некоторое предопределенное значение. O (1)
  • Minimum / Maximum (e): вернуть какое-то предопределенное значение. O (1)

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

  • Вставка (e): сравните значение e с минимальным / максимальным. Если условие выполнено, установите для минимума / максимума значение e. O (1)
  • Удалить (e): если mininum / максимум == e, то установить минимальный / максимальный как неизвестный (может быть NULL?). Иначе, просто удалите e из массива. O (1)
  • Минимум / максимум (e): если минимум / максимум неизвестен, найдите и установите минимум / максимум, используя алгоритм O (N). Если минимум / максимум известен, просто верните его. O (N) или O (1).

Плюсы и минусы

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

Answer 3

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

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

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