Студопедия

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника



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




Читайте также:
  1. A - Общие и связь для координации поиска и спасения
  2. Cоциологический анализ электорального процесса: проблемы и методы исследования, сферы применения результатов
  3. I. Коллективный анализ и целеполагание воспитатель­ной работы с привлечением родителей, учащихся, учите­лей класса.
  4. II. Рабочие определения, используемые при анализе литературного произведения
  5. O 6.Анализ и интерпретация результатов.
  6. PEST-анализ
  7. SWOT - анализ и его применение в маркетинговых исследованиях.
  8. Swot- Анализ
  9. SWOT-анализ
  10. SWOT-анализ 1 страница

Для отыскания искомого элемента с использованием алгоритмов линейного поиска в худшем случае придется просмотреть все N элементов массива, следовательно порядок функции ВС будет O(N). В лучшем случае, когда искомый элемент равен первому элементу массива, число сравнений не зависит от количества элементов в массиве и порядок функции ВС будет O(N).

Оценим среднее время алгоритма, при этом будем исходить из следующего:

пусть Pi – вероятность того, что будет осуществляться поиск элемента со значением ki; предположим, что , т.е. элемент со значением ki не будет отсутствовать (в массиве обязательно есть элемент, поиск которого осуществляется).

Среднее время ( ), как следует из алгоритма, пропорционально среднему числу операций сравнения ( ) и равно ~ = . Если ключи имеют одинаковую вероятность P1=P2=...PN=P, а также учитывая, что , N*P=1, P=1/N, тогда ,

т.е. при линейном поиске в среднем необходимо просмотреть половину массива.

Для экспериментального определения среднего числа сравнений необходимо найти суммарное число сравнений при поиске всех элементов массива и разделить на количество элементов.


Дата добавления: 2015-04-18; просмотров: 12; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2020 год. (0.017 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты