Линейный поиск: различия между версиями

329 байт добавлено ,  10 лет назад
нет описания правки
[непроверенная версия][непроверенная версия]
Нет описания правки
Нет описания правки
== Анализ ==
Для списка из ''n'' элементов лучшим случаем будет тот, при котором искомое значение равно первому элементу списка и требуется только одно сравнение. Худший случай будет тогда, когда значения в списке нет (или оно находится в самом конце списка), в случае чего необходимо ''n'' сравнений.
 
Если искомое значение входит в список ''k'' раз и все вхождения равновероятны, то ожидаемое число сравнений
 
:<math>
\begin{cases}
n & k = 0 \\[5pt]
\displaystyle\frac{n + 1}{k + 1} & 1 \le k \le n.
\end{cases}
</math>