Разработка системы задач (алгоритмы-программы) по дискретной математике — страница 3

  • Просмотров 3902
  • Скачиваний 207
  • Размер файла 88
    Кб

реализации перебора приводит к экспоненциальным алгоритмам. Действительно, Пусть все решения имеют длину N, тогда исследовать требуется порядка | Si| *| S2| *...*| SN| узлов дерева. Если значение S; ограничено некоторой константой С, то получаем порядка CN узлов. Поиск данных. Логарифмический(бинарный) поиск Логарифмический (бинарный или метод деления пополам) по­иск данных применим к сортированному множеству элементов а1 < а2 < ... < ап,

размещение которого выполнено на смежной па­мяти. Для большей эффективности поиска элементов надо, чтобы пути доступа к ним стали более короткими, чем просто последова­тельный перебор. Наиболее очевидный метод: начать поиск со среднего элемента, т.е. выполнить сравнение с элементом а. Результат сравнения позволит определить, в какой половине по­следовательности а{, а2,..., а, 1+„ ,,..., ап продолжить поиск, применяя к ней ту же

процедуру, и т.д. Основная идея бинарного поиска довольно проста, однако «для многих хороших програм­мистов не одна попытка написать правильную программу закон­чилась неудачей». Чтобы досконально разобраться в алгоритме, лучше всего представить данные ах < а2 < ... < ап в виде двоичного дерева сравнений, которое отвечает бинарному поиску. Двоичное дерево называется деревом сравнений , если для лю­бой его вершины (корня

дерева или корня поддерева) выполняет­ся условие: {Вершины левого поддерева}<Вершина корня<{Вершины правого поддерева }. Рис. Пример дерева сравнений, отвечающего бинарному поиску среди сортированных элементов: 3,5,7,9,12,19,27,44 Т.о. бинарный поиск – это сравнение эталона х, которое осуществляется с элементом, расположенным в середине массива и в зависимости от результата сравнения (больше или меньше) дальнейший поиск проводится в

левой или правой половине массива. Используется, когда имеется какая-либо информация о массиве, например массив упорядочен по неубыванию. Общее количество сравнений имеет порядок О(N*logN). Методы сортировки. Сортировка слияниями. Используется, когда необходимо объединить упорядоченные фрагменты массивов: A[k],…,A[m] и B[m+1],…,B[q] в один C[k],…,C[q], тоже упорядоченный (k<=m<=q). Основная идея решения состоит в сравнении очередных элементов

каждого фрагмента, выяснении, какой из элементов меньше, переносе его во вспомогательный массив С (для простоты) и продвижении по тому фрагменту массива, из которого взят элемент. При этом следует не забыть записать в С оставшуюся часть того фрагмента, который не успел себя «исчерпать». Метод слияний – один из первых в теории алгоритмов сортировки. Он предложен Дж. Фон Нейманом в 1945 году. Эффективность алгоритма, по Д. Кнуту,