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