анализ сложности линейного поиска в отсортированном массиве

Question

Может кто-нибудь сказать мне, какова будет средняя временная сложность линейного поиска, когда он применяется к отсортированному массиву? Я знаю, что в худшем случае будет O (n), а в лучшем случае будет O (1), но я не знаю о среднем случае в отсортированном массиве.

Answer 1

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

Теперь Для успешного поиска:

Нам может потребоваться выполнить 1 сравнение или 2, 3 или 4 и т. Д.

Следовательно, complexity(successful search) = 1 (1 / n) + 2 (1 / n) + 3 (1 / n) ..... n (1 / n) = (n + 1) / 2

Также учитывая неудачный поиск:

complexity(unsuccessful search) = n (поскольку мы рассмотрим весь массив, прежде чем рассматривать его как неудачный).

Теперь, если q вероятность успеха, 1-q будет вероятностью неудачной.

Следовательно, Средняя сложность = q * (n + 1) / 2 + (1- q) * n

Здесь q = 1/2

Средняя сложность = (3n + 1/4) ~ O (n)