Студопедия

КАТЕГОРИИ:

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


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




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

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

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

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

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

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


Поделиться:

Дата добавления: 2015-04-18; просмотров: 73; Мы поможем в написании вашей работы!; Нарушение авторских прав





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