Сколько элементов необходимо проверить в среднем при линейном поиске?

Question

Вопрос: рассмотрим линейный поиск. Сколько элементов входной последовательности необходимо проверить в среднем, если предположить, что искомый элемент с равной вероятностью будет любым элементом в массиве?

Как мне это решить? Нужно ли брать случай, когда элемент отсутствует в последовательности? В этом случае необходимо проверить все n элементов.

Всего № случаев (n + 1), Поэтому среднего нет. элементов для проверки = (1 + ... + n + n) / (n + 1), Этот ответ правильный?

Answer 1

Различают два случая, когда элемент находится в массиве (успешный поиск) и где его нет (неудачный поиск).

Для успешного поиска среднее значение составляет (1 + 2 + ... + n) / n = (n + 1) / 2.

Для неудачного поиска среднее значение равно n.

Общее среднее значение теперь зависит от сочетания успешных и неудачных поисков. Например, если большая часть поисков не удалась, он будет близок к n. Если все поиски успешны (это, кажется, то, что подразумевается под вопросом), среднее значение (n + 1) / 2.

Если вероятность успешного поиска равна p, и, следовательно, для неудачного поиска 1-p, мы получаем среднее значение p * (n+1) / 2 + (1-p) * n.