какая жесткая временная сложность ограничена для поиска в отсортированном массиве

Question

Например, при сортировке жесткая нижняя граница равна N * log (N), где N - размер массива

как насчет поиска в отсортированном массиве? Я думаю, что это журнал (N), но я не уверен на 100%.

также все основано на сравнениях, никакая другая внешняя память, кроме самого входного массива, не может быть использована

заранее спасибо

Answer 1

Я не совсем уверен, что означает жесткий, но я могу дать вам доказательство того, что O (log n) является нижней границей сложности задачи.

Сложность задачи говорит о сложности задачи в целом вместо алгоритма.

Существует только три результата сравнения элемента в массиве и заданного элемента:

array[i]=element: stop
array[i]<element: search the first half
array[i]>element: search the second half

Этот процесс может быть представлен двоичным деревом. В лучшем случае глубина дерева O (log n). Поэтому мы можем утверждать, что ни один алгоритм не будет быстрее, чем O (log n), что является нижней границей времени задачи.

Верхняя граница сложности задачи определяется наименьшей временной сложностью любого алгоритма, решающего задачу. Существует алгоритм двоичного поиска, сложность которого O (log n).

Что касается задачи поискового массива, то верхняя и нижняя границы совпадают, поэтому сложность задачи составляет O (log n).

Answer 2

Да: нижняя граница для поиска в отсортированном массиве с использованием только сравнений составляет o (log n) .

Для не совсем точного доказательства того, почему этоэто так, представьте дерево решений для любого алгоритма, решающего эту проблему.Количество листовых узлов в дереве равно n + 1 (один результат для каждой позиции и результат «не найден»).Таким образом, минимальная глубина этого дерева должна быть порядка log₂ n .

Answer 3

Оптимальным решением для поиска простого отсортированного массива является двоичный поиск, который имеет временную сложность O (log₂ (N)) .Наихудший случай случается, когда искомый элемент отсутствует в массиве и занимает ровно ⌊log⌊ (N) + 1⌋ итераций.См. Производительность бинарного поиска .

Я полагаю, что вы можете говорить о «сжатости» только при обращении к верхним и нижним пределам сложности.Нижняя граница (большая Омега), как правило, сложнее вычислить, и часто она не так полезна, как верхняя граница (большая О).Tight bound (big Theta) учитывает как верхнюю, так и нижнюю границы.

Технически нижняя граница - это Ω (1), потому что вы можете найти искомый элемент при первом сравнении.См. Является ли бинарный поиск тэта log (n) или большой O log (n) для дальнейшего обсуждения временной сложности бинарного поиска.