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

289 байт добавлено ,  10 лет назад
[непроверенная версия][непроверенная версия]
</math>
 
Например, если искомое значение встречается в списке один раз, и все вхождения равновероятны, то ожидаемоесреднее число сравнений равно <math>\frac{n + 1}2</math>.
Однако, если ''известно'', что оно встречается один раз, то достаточно ''n'' - 1 сравнений и ожидаемоесреднее число сравнений будет равняться
:<math>\displaystyle\frac{(n + 2)(n-1)}{2n}</math>
 
(для ''n'' = 2 это число равняется 1, что соответствует одной конструкции if-then-else).
 
В любом случае, [[вычислительная сложность]] алгоритма [[«O» большое и «o» малое|O]](''n'').
 
== Литература ==