#c #c #algorithm #sorting #data-structures
#c #c #алгоритм #сортировка #структуры данных
Вопрос:
Возможно ли это, чтобы найти наименьший элемент массива неотсортированных целых чисел быстрее, чем O (n) временная сложность. Сложность пространства не вызывает беспокойства.
Комментарии:
1. Единственный способ выполнить поиск быстрее, чем
O(n), — это сначала получить отсортированный массив.2. @Cyber Некоторые другие ограничения по списку могут привести к более быстрому поиску, чем
O(n). Не только ограничение «отсортированности».3. @Jefffrey Да (например, «первый элемент является минимальным», как в двоичных минимальных кучах), хотя это не влияет на ответ здесь, поскольку такого ограничения нет.
4. С квантовой сортировкой Bogo это возможно! c2.com/cgi/wiki ? QuantumBogoSort
5. Вероятно, это можно было бы сделать за O (log N), используя O (N) процессоры
Ответ №1:
Нет, это невозможно. Учитывая произвольный массив элементов, вы должны посмотреть на каждый элемент хотя бы один раз, чтобы окончательно заявить, что вы нашли минимальный элемент. Это означает, что необходимая временная сложность составляет Ω(n) (смотрите здесь для получения дополнительной информации о нотации Big Omega), что означает *, что любой алгоритм, который находит минимальный элемент, будет выполнять по меньшей мере c * n операции, где c является постоянной (в данном случае, c >= 1 ).
Другими словами, если алгоритм потребовал меньше n операций, то в массиве должен быть хотя бы один элемент, который алгоритм не пропустил. Поскольку у нас нет информации об этом элементе (массив произвольный), мы не можем сказать, что этот элемент не меньше элемента, объявленного алгоритмом минимальным. Итак, алгоритм неверен.
* Обратите внимание, что это не является формальным значением обозначения Big-Omega, но оно передает суть. Вы можете прочитать о формальном определении здесь.
Комментарии:
1. Я отредактировал ответ. Пожалуйста, просмотрите это. Откат, если вы сочтете правку неуместной.
2. @Nawaz Разве ответ не имел бы смысла с «не» или без него? Вы не можете знать, меньше ли элемент min, но вы ТАКЖЕ не можете знать, не меньше ли он min. Вы буквально ничего не знаете, поскольку следующий элемент может полностью изменить ответ в любом случае.
3. @RickyMutschlechner Это тоже была моя логика, но я думаю, что правка Наваза более уместна, поскольку мы пытаемся найти минимальный элемент, поэтому, не имея возможности сказать, что элемент не меньше, вы не можете утверждать, что алгоритм правильный.
4. @Daniel ах, да. Доказательство правильности. Справедливо!