Программная реализация и анализ алгоритмов поиска - курсовая работа готовая

Курсовая работа на тему Программная реализация и анализ алгоритмов поиска

Перед первой итерацией определяется средний элемент в данном списке. При сравнении целевого значения со средним элементом отсортированного списка возможен один из трех результатов: значения равны, целевое значение меньше элемента списка, либо целевое значение больше элемента списка. В первом, и наилучшем, случае поиск завершен. В остальных двух случаях мы можем отбросить половину списка.
Когда целевое значение меньше среднего элемента, то можно сделать вывод, что если оно имеется в списке, то находится перед этим средним элементом. Когда же оно больше среднего элемента и оно имеется в списке, то находится после этого среднего элемента. Этого достаточно, чтобы мы могли одним сравнением отбросить половину списка. При повторении этой процедуры мы сможем отбросить половину оставшейся части списка.
Таким образом, повторяя раз за разом данное деление списка по пополам, будет либо обнаружен искомый элемент, либо будет ясно, что он отсутствует.
1.2.1 Блок-схема алгоритма бинарного поиска

1.2.2 Анализ сложности алгоритма
Анализ наихудшего случая.
При каждом делении списка пополам, то есть с каждой итерацией цикла, степень двойки в длине оставшейся части списка уменьшится на 1, а также. Когда происходит последняя итерация цикла, размер оставшейся части становится равным 1, а это происходит при k=1 (так как 21 -1=1). Это означает, что при N=2k -1 число проходов не превышает k. Решая последние уравнение относительно k выходит, что в наихудшем случае число проходов равно k=log2 (N+1).
Анализ среднего случая.
В среднем случае сложность можно оценить, используя ту же схему рассмотрения, но находя среднее число итераций по всем элементам массива.
в общем виде отличается от формулы не более, чем на 0,5.
Таким образом, алгоритм обладает логарифмической временной сложностью по данным.

Поделиться статьёй
Поделиться в telegram
Поделиться в whatsapp
Поделиться в vk
Поделиться в facebook
Поделиться в twitter
Леонид Федотов
Леонид Федотов
Окончил НИУ ВШЭ факультет компьютерных наук. Сам являюсь кандидатом наук. По специальности работаю 13 лет, за это время создал 8 научных статей и 2 диссертации. В компании подрабатываю в свободное от работы время уже более 5 лет. Нравится помогать школьникам и студентам в решении контрольных работ и написании курсовых проектов. Люблю свою профессию за то, что это направление с каждым годом становится все более востребованным и актуальным.

Ещё статьи