Алгоритм как упражнение

Question

Таким образом, большинство должно знать, что max_element(unsorted_array) может быть решено за O(n) время.Я понял, что хотя это легко вычислить, кажется, что будет гораздо сложнее решить его в менее оптимальном решении, таком как n*log(log(n)) время.Теперь очевидно, что алгоритм может быть просто O(n + n*log(log(n)) ), где более трудоемкая часть алгоритма не имеет реальной цели.В то же время вы можете просто использовать обычный O(n) алгоритм log(log(n)) раз.Ни один из них не очень интересен.

Поэтому мой вопрос заключается в том, существует ли алгоритм, который может найти элемент max в наборе чисел (хранящемся в выбранном вами контейнере) таким образом, чтобы не было избыточныхциклы или операции, но это 100 (n*log(log(n)))?

Answer 1

Деревья Ван Эмде Боаса ?

Answer 2

Здесь есть базовое заблуждение:

O (n + n * log (log (n))) в точности совпадает с O (n log (log (n))) *

Пожалуйста, внимательно прочитайте страницу вики: http://en.wikipedia.org/wiki/Big_O_notation

Обозначение Big-O асимптотическое.Это означает, что O (f (n) + g (n)) = O (max (f (n), g (n))) для всех функций f, g.Это не уловка, они действительно равны.

Символы, такие как O (n ^ 2), O (n) и т. Д., Являются , а не функциями, они являются наборами;в частности, O (f (n)) означает «множество всех функций, которые асимптотически меньше или равны постоянному времени f (n)».Если f (n)> = g (n), то O (f (n)) содержит O (g (n)), поэтому добавление g (n) в это уравнение ничего не меняет.

Answer 3

Как насчет доказательства того, что это невозможно сделать?

Теория: можно определить максимальный элемент несортированного массива без проверки каждого элемента.

• Предположим, что вы изучили все элементы, кроме одного, из несортированного массива из n (n> 1) элементов.
• Есть две возможности для самого большого элемента массива.
  • Самый большой элемент, который вы когда-либо видели (из n-1).
  • Один элемент, который вы не видели

Неисследованный элемент может быть больше (если только исследуемый элемент не является абсолютным максимальным представимым значением); массив не отсортирован.

Результат: противоречие. Вы должны исследовать n-й элемент, чтобы определить максимум (в контексте математики; вы можете использовать ярлык в области компьютерных наук при одном, вероятно, редком случае)

Поскольку не имеет значения, какое значение n имеет для этого, оно должно применяться ко всем n, кроме вырожденного случая (n = 1)

Если это неправильный ответ, я могу быть неясным относительно требований ...?