Методика сравнительного анализа алгоритмов на примере алгоритмов последовательного поиска
Международная
публикация
С.
В. СамуйловБиблиографическое описание статьи для цитирования:
Самуйлов
С.
В. Методика сравнительного анализа алгоритмов на примере алгоритмов последовательного поиска // Научно-методический электронный журнал «Концепт». –
2014. – № 9 (сентябрь). – С.
46–50. – URL:
http://e-koncept.ru/2014/14236.htm.
Аннотация. Статья посвящена актуальным вопросам обучения студентов методам сравнения, анализа и выбора алгоритма для решения поставленной задачи на примере сравнительного анализа алгоритмов последовательного поиска.
Текст статьи
Самуйлов Сергей Владимирович,кандидат технических наук, заведующий кафедрой «Информатика, математика и общегуманитарные науки» ФГОБУ ВПО «Финансовый университет при Правительстве Российской Федерации» (Пензенский филиал), г. Пензаsws_p@mail.ru
Методика сравнительного анализа алгоритмов на примере алгоритмов последовательного поиска
Аннотация. Статья посвящена актуальным вопросам обучения студентов методам сравнения, анализа и выбора алгоритма для решения поставленной задачи на примере сравнительного анализа алгоритмов последовательного поиска. Ключевые слова: сравнение и анализ алгоритмов, последовательный поиск, самоорганизующиеся таблицы.Раздел: (01)педагогика; история педагогики и образования; теория и методика обучения и воспитания (по предметным областям).
Для решения большинства задач, как правило, существует много различных алгоритмов, которые могут отличаться друг от друга по быстродействию, требуемой внутренней и/или внешней памяти, сложности программирования и ряду других критериев. Приэтом, как правило, не существует алгоритма, которыйбыл бы предпочтительнее при любых исходных данных и по всем критериям оценки. Какой из них выбрать для решения конкретной задачи? Этот вопрос очень важен для любого профессионального программиста. Именно поэтому необходимо уже на ранних этапах обучения студентов «программистских» направлений подготовки уделять как можно больше времени вопросам выбора эффективного алгоритма решения задачи. Начинающий программист должен четко понимать, что один из основных этапов решения любой задачи –анализ и выбор алгоритма ее решения.Традиционный способ сравнения эффективности алгоритмов состоит в сопоставлении их порядков сложности. Этот метод применим как к временной, так и пространственной сложности. Порядок сложности алгоритма выражает его эффективность обычно черезколичество обрабатываемых данных.Однако такой подход к оценке эффективности алгоритмов имеет ряд недостатков. Одним из основных недостатковOфункций является их чрезмерная грубость. Если алгоритм А выполняет некоторую задачу за 0,001×N секунд, в то время как для ее же решения с помощью алгоритма В требуется 1000×N секунд, то алгоритм А в миллион раз быстрее, чем алгоритм В. Тем не менее А и В имеют одну и ту же временную сложность O(N).Следовательно, очень часто необходим более детальный анализ алгоритмов, претендующих на решение одной и той же задачи. В статье рассматривается методика сравнительного анализа различных алгоритмов на примере алгоритмов последовательного поиска. Выбор данной группы алгоритмов основан на том, что последовательный поиск очень часто применяется и в повседневнойжизни, он интуитивно понятен ина первыйвзглядтривиален. Казалось бы, что можно улучшить в простом последовательном переборе?Но начнем всетаки с того, что знание алгоритмов последовательного поиска профессиональному программисту крайне необходимо. Представьте себе, что необходимо найти книгу в книжном шкафу, расположение книг в котором неизвестно. Так как книгу найти всетаки нужно, то в этом случае очевидный подход –простой последовательный перебор всех находящихся в шкафу книг. Если повезет, вы затратите только одно сравнение, в худшем случае –Nсравнений, где N–количество книг в шкафу. Среднее число сравнений, т.е. если поиск книг будет повторяться многократно, равен N/2. Таким образом, если мы ничего не знаем об организации исходных данных (например, исходные данные могут быть упорядочены), то, скорее всего, без использования последовательного поиска не обойтись.Сформулируем алгоритм более точно. Пусть имеется массив записей с ключами K1, K2, ..., Kn. Необходимо найти запись с заданным ключом K. Тогда традиционный алгоритм последовательного поиска будет включать следующие шаги (алгоритм А) [1].1.i= 1.2.Если K Ki, алгоритм заканчивается удачно.3.Иначе i i + 1.4.Если i < N, то вернуться к шагу 2. 5.Иначе алгоритм заканчивается неудачно.Сложность алгоритма неоптимального последовательного поиска (алгоритма А) определяется как О(n).Условия окончания поиска следующие.1.Элемент найден, т.е. обнаружен ключ Ki= K.2.Все записи просмотрены, и совпадение не обнаружено (i > N).Приведенный выше алгоритм при всей своей очевидности не является, однако,оптимальным. В алгоритме А имеются две проверки: на совпадение ключей и на выход значения индекса за пределы массива.Если гарантировать, что ключ всегда будет найден, то без второго условия (выход индекса за границу массива) можно обойтись. Для этого достаточно в конце массива –(N+1)й элемент–поместить дополнительный элемент, присвоив ему значение искомого ключа K. Назовем такой вспомогательный элемент «барьером», так как он предотвращает выход за пределы массива.Таким образом, ключ всегда будет найден в записи с индексом i. При i N+1 (индекс достиг концамассива) ключ не найден (т.е. найден только в барьере), поиск неудачен. В противном случае –поиск удачен. Алгоритм, реализующий описанный выше метод поиска, можно назвать алгоритмом оптимального последовательного поиска (алгоритм В). Рассмотрим его более подробно.1.Kn+1 = K.2.i = 1.3.Если K Ki, на шаг 5.4.Иначе i i + 1. На шаг 3.5.Если i N+1, то поиск неудачен (ключ найден в барьере), иначе –поиск удачен (ключнайден в iм элементе массива).Сложность алгоритма оптимального последовательного поиска (алгоритма В) также определяется как О(n), однако рассмотренный выше алгоритм В позволяет исключить в среднем (N + 1)/2 сравнений. Для сравнения описанных выше алгоритмов была написана программа, замеряющая время поиска m ключей в неупорядоченном массиве из m записей с помощью как алгоритма А, так и алгоритма В. Переменная m меняется от 5000 до 100000 с шагом 5000. Результаты работы программы приведены на рис.1.
Как показывает график, алгоритм оптимального последовательного поиска (алгоритм В) примерно в два раза быстрее алгоритма неоптимального последовательного поиска (алгоритм А).
Рис. 1. Сравнение алгоритма А и алгоритма В
Дальнейшая оптимизация алгоритма последовательного поиска возможна лишь путем некоторой предварительной организации данных. Рассмотрим два варианта такой организации: упорядочение исходных данных и использование самоорганизующихся таблиц.Самый широко применяемый способ организации исходных данных –это их упорядочение. Очень часто исходные данные изначально упорядочены, и в этомслучае для поиска эффективней применять более быстрые алгоритмы поиска, например бинарный поиск (сложность О(log2(n)).Однакоалгоритмы последовательного поиска очень часто используются и для поиска в упорядоченных массивах. Если поиск необходимо осуществить однократноили поиск осуществляется в массиве небольшой размерности,использовать более сложные алгоритмы поиска нецелесообразно. Рассмотрим особенности применения алгоритма последовательного поиска для упорядоченной последовательности исходных данных.Если известно, что ключи упорядочены (например, расположены в возрастающем порядке), то алгоритм последовательного поиска целесообразно несколько изменить.Пусть имеется множество записей с ключами K1, K2, ..., Kn, причем K1≤K2≤...≤Kn. Необходимо найти запись с заданным ключом K. В целях увеличения скорости работы в конец массива также помещается дополнительный элемент –«барьер», значение которого должно быть больше значения искомого ключа K (например, K+1).В отличие от поиска в неупорядоченном массиве просмотр элементов упорядоченного массива заканчивается в тот момент, когда первый раз выполнится условие K ≤ Ki. Очевидно, что все элементы Ki+1, ..., Kn будут больше K.Если K Ki –поиск удачен. В противном случаеискомого элемента нет в массиве. Тогда алгоритм поиска в упорядоченном массиве будет включать следующие шаги (алгоритм С).1.Kn+1 = K+1.2.i = 1.3.Если K < Ki, на шаг 5.4.Иначе i i + 1, на шаг 3.5.Если K Ki, то поиск удачен, иначе –поиск неудачен.В случае удачного поиска алгоритм поиска в упорядоченном массиве не лучше алгоритма поиска в неупорядоченном массиве, однакоотсутствие нужного ключа этот алгоритм позволяет обнаружить в среднем в два раза быстрее.Для сравнения времени работы алгоритма В и алгоритма С в описанной выше программе вместо неупорядоченного массива использовался упорядоченный. Результаты работы программы приведены на рис.2.
Рис. 2. Сравнение алгоритма В и алгоритма С
Очевидно, что алгоритм С будет тем более эффективнее алгоритма В, чем чаще поиск оказывается неудачным. На рис.2 приведен пример, отражающий время поиска для случая, когда примерно каждый второй поиск неудачен.Выше был приведентрадиционный подход к организации последовательного поиска. В рассмотренных выше алгоритмах предполагается, что поиск любого из ключей может потребоваться с равной вероятностью. Однако часто такое предположение ложно. Например, какието книги в библиотеке выдаются читателям чаще, какието реже, телефоны вокзалов, поликлиник и некоторых магазинов в справочной службе спрашивают чаще и т.п.
Нижекак альтернатива общеизвестным алгоритмам последовательного поискарассматривается один из малоисследованных и редко применяемых методов организации и поиска данных –самоорганизующиеся таблицы[2].Пусть вероятность поиска ключа Ki равна pi, гдеp1 + p2 + . . . + pn = 1.Очевидно, что число сравнений при поиске будет минимально, еслиp1 ≥ p2 ≥ . . . ≥ pn,т.е. когда наиболее часто используемые записи находятся в начале таблицы.Однако в большинстве случаев распределение вероятностей нам неизвестно. Более того, эти вероятности зачастую не являются константами и со временем изменяются. Рассмотрим методы решения задачи последовательного поиска с использованием самоорганизующихся таблиц.Метод перемещения в начало. Данный метод использует следующую простую схему. Когда будет найдена нужная запись, она помещается в начало таблицы.Такая схема позволяет довольно хорошо упорядочить записи без использования вспомогательных полей для счетчика. В результате часто используемые элементы будут располагаться довольно близко к началу.Метод перемещения в начало наиболее легко реализовать, когда данные представлены в виде связанного линейного списка.Метод транспозиции. В данном методе извлеченная запись меняется местами с записью, которая ей предшествует.Два описанных выше метода достаточно просты и в понимании, и в реализации. Однако следующие вопросы необходимо всетаки исследовать. 1.В какой момент таблица уже настолько «организована», что дальнейшая самоорганизация не приводит к существенным улучшениям?2.Какой из двух рассмотренных выше методов более эффективен?Итак, у нас есть исходный массив М, в котором ключи располагаются произвольно относительно вероятности их поиска. Введем понятие «идеальный массив» , т.е. массив, упорядоченный по убыванию вероятности поиска.Для каждого iго элемента массива М можно вычислить i –расстояние между его положением в массивах М и . Тогда величина
и будет определять степень «организованности» массива М. Очевидно, что R 0.Понятно, что с каждым новым поиском массив М будет все больше «организовываться», а значение R стремиться к нулю. Однако, как будет показано ниже, идеального состояния массив М так и не достигает. Поэтому для ответа на первый поставленный вопрос необходимо экспериментально подсчитать для массива М из n элементов то количество поисков, которого достаточно для максимальной организации исходного массива М. На рис.3 приведен график зависимости величины RM от количества произведенных в массиве поисков для метода транспозиции при n 100.
Рис. 3. Метод транспозиции
Тот же самый процесс для метода перемещения в начало приведен на рис.4.
Из рис.3 видно, что примерно после 19000 сравнений массив из 100 элементов приходим к максимальной организации, т.е. дальнейшая самоорганизация массива не приводит к улучшениям.Также очевидно, что метод транспозиции, в конце концов, дает более эффективный поиск, чем метод перемещения в начало для тех таблиц, в которых вероятность доступа к некоей конкретной записи остается постоянной во времени.Однако метод транспозиции требует большего времени для достижения максимальной эффективности, чем метод перемещения в начало. Поэтому может быть рекомендована некоторая смешанная стратегия, при которой первоначально используется метод перемещения в начало, что позволит быстро переупорядочить таблицу, а затем использовать метод транспозиции для поддержания данной таблицы в относительном порядке.Другим преимуществом метода транспозиции является то, что он может быть одинаково эффективно применен к таблицам, представленным в виде массиваи в виде списка.Завершая рассмотрение алгоритмов последовательного поиска,можно сделать вывод, что, несмотря на кажущуюся простоту базового алгоритма последовательного поиска (алгоритма А), его незначительные улучшения приводят к существенному повышению эффективности последовательного поиска.
Рис. 4. Метод перемещения в начало
Ссылки наисточники1.Структуры и алгоритмы компьютерной обработки данных: учеб.пособие / А.Б. Баканов, В.В.Дрождин, С.В. Самуйлов; Пензенский гос. пед. унт им. В. Г. Белинского. –Пенза, 2007.2.Структурыданных: учеб.пособие / И.А.Казакова, С.В. Самуйлов; Мво образования и науки РФ, Гос. образовательное учреждение высш. проф. образования «Пензенский гос. унт»(ПГУ).–Пенза, 2011.
SergeySamuylov,Candidate of Engineering Sciences, head of the chair of computer sciences, mathematics and the humanities, Financial University under the Government of the Russian Federation, Penza branch, Penzasws_p@mail.ruTechnique of the comparative analysis of algorithms on the example of algorithms of consecutive searchAbstract. The article is devoted to topical issues of training students to methods of comparison, analysis and algorithm choice for the solution of an objective on the example of the comparative analysis of algorithms of consecutive search. Key words: comparison and analysis of algorithms, consecutive search, selforganizing tables.References1.Bakanov, A. B.,Drozhdin, V. V. & Samujlov, S. V. (2007) Struktury i algoritmy komp'juternoj obrabotki dannyh: ucheb. Posobie, Penzenskij gos. ped. unt im. V. G. Belinskogo, Penza (in Russian).2.Kazakova, I. A. & Samujlov, S. V. (2011) Struktury dannyh: ucheb. posobie,Mvo obrazovanija i nauki RF, Gos. obrazovatel'noe uchrezhdenie vyssh. prof. obrazovanija “Penzenskij gos. unt” (PGU), Penza, (in Russian).
Рекомендованокпубликации:
ГоревымП. М.,кандидатомпедагогическихнаук, главнымредакторомжурнала«Концепт»
Методика сравнительного анализа алгоритмов на примере алгоритмов последовательного поиска
Аннотация. Статья посвящена актуальным вопросам обучения студентов методам сравнения, анализа и выбора алгоритма для решения поставленной задачи на примере сравнительного анализа алгоритмов последовательного поиска. Ключевые слова: сравнение и анализ алгоритмов, последовательный поиск, самоорганизующиеся таблицы.Раздел: (01)педагогика; история педагогики и образования; теория и методика обучения и воспитания (по предметным областям).
Для решения большинства задач, как правило, существует много различных алгоритмов, которые могут отличаться друг от друга по быстродействию, требуемой внутренней и/или внешней памяти, сложности программирования и ряду других критериев. Приэтом, как правило, не существует алгоритма, которыйбыл бы предпочтительнее при любых исходных данных и по всем критериям оценки. Какой из них выбрать для решения конкретной задачи? Этот вопрос очень важен для любого профессионального программиста. Именно поэтому необходимо уже на ранних этапах обучения студентов «программистских» направлений подготовки уделять как можно больше времени вопросам выбора эффективного алгоритма решения задачи. Начинающий программист должен четко понимать, что один из основных этапов решения любой задачи –анализ и выбор алгоритма ее решения.Традиционный способ сравнения эффективности алгоритмов состоит в сопоставлении их порядков сложности. Этот метод применим как к временной, так и пространственной сложности. Порядок сложности алгоритма выражает его эффективность обычно черезколичество обрабатываемых данных.Однако такой подход к оценке эффективности алгоритмов имеет ряд недостатков. Одним из основных недостатковOфункций является их чрезмерная грубость. Если алгоритм А выполняет некоторую задачу за 0,001×N секунд, в то время как для ее же решения с помощью алгоритма В требуется 1000×N секунд, то алгоритм А в миллион раз быстрее, чем алгоритм В. Тем не менее А и В имеют одну и ту же временную сложность O(N).Следовательно, очень часто необходим более детальный анализ алгоритмов, претендующих на решение одной и той же задачи. В статье рассматривается методика сравнительного анализа различных алгоритмов на примере алгоритмов последовательного поиска. Выбор данной группы алгоритмов основан на том, что последовательный поиск очень часто применяется и в повседневнойжизни, он интуитивно понятен ина первыйвзглядтривиален. Казалось бы, что можно улучшить в простом последовательном переборе?Но начнем всетаки с того, что знание алгоритмов последовательного поиска профессиональному программисту крайне необходимо. Представьте себе, что необходимо найти книгу в книжном шкафу, расположение книг в котором неизвестно. Так как книгу найти всетаки нужно, то в этом случае очевидный подход –простой последовательный перебор всех находящихся в шкафу книг. Если повезет, вы затратите только одно сравнение, в худшем случае –Nсравнений, где N–количество книг в шкафу. Среднее число сравнений, т.е. если поиск книг будет повторяться многократно, равен N/2. Таким образом, если мы ничего не знаем об организации исходных данных (например, исходные данные могут быть упорядочены), то, скорее всего, без использования последовательного поиска не обойтись.Сформулируем алгоритм более точно. Пусть имеется массив записей с ключами K1, K2, ..., Kn. Необходимо найти запись с заданным ключом K. Тогда традиционный алгоритм последовательного поиска будет включать следующие шаги (алгоритм А) [1].1.i= 1.2.Если K Ki, алгоритм заканчивается удачно.3.Иначе i i + 1.4.Если i < N, то вернуться к шагу 2. 5.Иначе алгоритм заканчивается неудачно.Сложность алгоритма неоптимального последовательного поиска (алгоритма А) определяется как О(n).Условия окончания поиска следующие.1.Элемент найден, т.е. обнаружен ключ Ki= K.2.Все записи просмотрены, и совпадение не обнаружено (i > N).Приведенный выше алгоритм при всей своей очевидности не является, однако,оптимальным. В алгоритме А имеются две проверки: на совпадение ключей и на выход значения индекса за пределы массива.Если гарантировать, что ключ всегда будет найден, то без второго условия (выход индекса за границу массива) можно обойтись. Для этого достаточно в конце массива –(N+1)й элемент–поместить дополнительный элемент, присвоив ему значение искомого ключа K. Назовем такой вспомогательный элемент «барьером», так как он предотвращает выход за пределы массива.Таким образом, ключ всегда будет найден в записи с индексом i. При i N+1 (индекс достиг концамассива) ключ не найден (т.е. найден только в барьере), поиск неудачен. В противном случае –поиск удачен. Алгоритм, реализующий описанный выше метод поиска, можно назвать алгоритмом оптимального последовательного поиска (алгоритм В). Рассмотрим его более подробно.1.Kn+1 = K.2.i = 1.3.Если K Ki, на шаг 5.4.Иначе i i + 1. На шаг 3.5.Если i N+1, то поиск неудачен (ключ найден в барьере), иначе –поиск удачен (ключнайден в iм элементе массива).Сложность алгоритма оптимального последовательного поиска (алгоритма В) также определяется как О(n), однако рассмотренный выше алгоритм В позволяет исключить в среднем (N + 1)/2 сравнений. Для сравнения описанных выше алгоритмов была написана программа, замеряющая время поиска m ключей в неупорядоченном массиве из m записей с помощью как алгоритма А, так и алгоритма В. Переменная m меняется от 5000 до 100000 с шагом 5000. Результаты работы программы приведены на рис.1.
Как показывает график, алгоритм оптимального последовательного поиска (алгоритм В) примерно в два раза быстрее алгоритма неоптимального последовательного поиска (алгоритм А).
Рис. 1. Сравнение алгоритма А и алгоритма В
Дальнейшая оптимизация алгоритма последовательного поиска возможна лишь путем некоторой предварительной организации данных. Рассмотрим два варианта такой организации: упорядочение исходных данных и использование самоорганизующихся таблиц.Самый широко применяемый способ организации исходных данных –это их упорядочение. Очень часто исходные данные изначально упорядочены, и в этомслучае для поиска эффективней применять более быстрые алгоритмы поиска, например бинарный поиск (сложность О(log2(n)).Однакоалгоритмы последовательного поиска очень часто используются и для поиска в упорядоченных массивах. Если поиск необходимо осуществить однократноили поиск осуществляется в массиве небольшой размерности,использовать более сложные алгоритмы поиска нецелесообразно. Рассмотрим особенности применения алгоритма последовательного поиска для упорядоченной последовательности исходных данных.Если известно, что ключи упорядочены (например, расположены в возрастающем порядке), то алгоритм последовательного поиска целесообразно несколько изменить.Пусть имеется множество записей с ключами K1, K2, ..., Kn, причем K1≤K2≤...≤Kn. Необходимо найти запись с заданным ключом K. В целях увеличения скорости работы в конец массива также помещается дополнительный элемент –«барьер», значение которого должно быть больше значения искомого ключа K (например, K+1).В отличие от поиска в неупорядоченном массиве просмотр элементов упорядоченного массива заканчивается в тот момент, когда первый раз выполнится условие K ≤ Ki. Очевидно, что все элементы Ki+1, ..., Kn будут больше K.Если K Ki –поиск удачен. В противном случаеискомого элемента нет в массиве. Тогда алгоритм поиска в упорядоченном массиве будет включать следующие шаги (алгоритм С).1.Kn+1 = K+1.2.i = 1.3.Если K < Ki, на шаг 5.4.Иначе i i + 1, на шаг 3.5.Если K Ki, то поиск удачен, иначе –поиск неудачен.В случае удачного поиска алгоритм поиска в упорядоченном массиве не лучше алгоритма поиска в неупорядоченном массиве, однакоотсутствие нужного ключа этот алгоритм позволяет обнаружить в среднем в два раза быстрее.Для сравнения времени работы алгоритма В и алгоритма С в описанной выше программе вместо неупорядоченного массива использовался упорядоченный. Результаты работы программы приведены на рис.2.
Рис. 2. Сравнение алгоритма В и алгоритма С
Очевидно, что алгоритм С будет тем более эффективнее алгоритма В, чем чаще поиск оказывается неудачным. На рис.2 приведен пример, отражающий время поиска для случая, когда примерно каждый второй поиск неудачен.Выше был приведентрадиционный подход к организации последовательного поиска. В рассмотренных выше алгоритмах предполагается, что поиск любого из ключей может потребоваться с равной вероятностью. Однако часто такое предположение ложно. Например, какието книги в библиотеке выдаются читателям чаще, какието реже, телефоны вокзалов, поликлиник и некоторых магазинов в справочной службе спрашивают чаще и т.п.
Нижекак альтернатива общеизвестным алгоритмам последовательного поискарассматривается один из малоисследованных и редко применяемых методов организации и поиска данных –самоорганизующиеся таблицы[2].Пусть вероятность поиска ключа Ki равна pi, гдеp1 + p2 + . . . + pn = 1.Очевидно, что число сравнений при поиске будет минимально, еслиp1 ≥ p2 ≥ . . . ≥ pn,т.е. когда наиболее часто используемые записи находятся в начале таблицы.Однако в большинстве случаев распределение вероятностей нам неизвестно. Более того, эти вероятности зачастую не являются константами и со временем изменяются. Рассмотрим методы решения задачи последовательного поиска с использованием самоорганизующихся таблиц.Метод перемещения в начало. Данный метод использует следующую простую схему. Когда будет найдена нужная запись, она помещается в начало таблицы.Такая схема позволяет довольно хорошо упорядочить записи без использования вспомогательных полей для счетчика. В результате часто используемые элементы будут располагаться довольно близко к началу.Метод перемещения в начало наиболее легко реализовать, когда данные представлены в виде связанного линейного списка.Метод транспозиции. В данном методе извлеченная запись меняется местами с записью, которая ей предшествует.Два описанных выше метода достаточно просты и в понимании, и в реализации. Однако следующие вопросы необходимо всетаки исследовать. 1.В какой момент таблица уже настолько «организована», что дальнейшая самоорганизация не приводит к существенным улучшениям?2.Какой из двух рассмотренных выше методов более эффективен?Итак, у нас есть исходный массив М, в котором ключи располагаются произвольно относительно вероятности их поиска. Введем понятие «идеальный массив» , т.е. массив, упорядоченный по убыванию вероятности поиска.Для каждого iго элемента массива М можно вычислить i –расстояние между его положением в массивах М и . Тогда величина
и будет определять степень «организованности» массива М. Очевидно, что R 0.Понятно, что с каждым новым поиском массив М будет все больше «организовываться», а значение R стремиться к нулю. Однако, как будет показано ниже, идеального состояния массив М так и не достигает. Поэтому для ответа на первый поставленный вопрос необходимо экспериментально подсчитать для массива М из n элементов то количество поисков, которого достаточно для максимальной организации исходного массива М. На рис.3 приведен график зависимости величины RM от количества произведенных в массиве поисков для метода транспозиции при n 100.
Рис. 3. Метод транспозиции
Тот же самый процесс для метода перемещения в начало приведен на рис.4.
Из рис.3 видно, что примерно после 19000 сравнений массив из 100 элементов приходим к максимальной организации, т.е. дальнейшая самоорганизация массива не приводит к улучшениям.Также очевидно, что метод транспозиции, в конце концов, дает более эффективный поиск, чем метод перемещения в начало для тех таблиц, в которых вероятность доступа к некоей конкретной записи остается постоянной во времени.Однако метод транспозиции требует большего времени для достижения максимальной эффективности, чем метод перемещения в начало. Поэтому может быть рекомендована некоторая смешанная стратегия, при которой первоначально используется метод перемещения в начало, что позволит быстро переупорядочить таблицу, а затем использовать метод транспозиции для поддержания данной таблицы в относительном порядке.Другим преимуществом метода транспозиции является то, что он может быть одинаково эффективно применен к таблицам, представленным в виде массиваи в виде списка.Завершая рассмотрение алгоритмов последовательного поиска,можно сделать вывод, что, несмотря на кажущуюся простоту базового алгоритма последовательного поиска (алгоритма А), его незначительные улучшения приводят к существенному повышению эффективности последовательного поиска.
Рис. 4. Метод перемещения в начало
Ссылки наисточники1.Структуры и алгоритмы компьютерной обработки данных: учеб.пособие / А.Б. Баканов, В.В.Дрождин, С.В. Самуйлов; Пензенский гос. пед. унт им. В. Г. Белинского. –Пенза, 2007.2.Структурыданных: учеб.пособие / И.А.Казакова, С.В. Самуйлов; Мво образования и науки РФ, Гос. образовательное учреждение высш. проф. образования «Пензенский гос. унт»(ПГУ).–Пенза, 2011.
SergeySamuylov,Candidate of Engineering Sciences, head of the chair of computer sciences, mathematics and the humanities, Financial University under the Government of the Russian Federation, Penza branch, Penzasws_p@mail.ruTechnique of the comparative analysis of algorithms on the example of algorithms of consecutive searchAbstract. The article is devoted to topical issues of training students to methods of comparison, analysis and algorithm choice for the solution of an objective on the example of the comparative analysis of algorithms of consecutive search. Key words: comparison and analysis of algorithms, consecutive search, selforganizing tables.References1.Bakanov, A. B.,Drozhdin, V. V. & Samujlov, S. V. (2007) Struktury i algoritmy komp'juternoj obrabotki dannyh: ucheb. Posobie, Penzenskij gos. ped. unt im. V. G. Belinskogo, Penza (in Russian).2.Kazakova, I. A. & Samujlov, S. V. (2011) Struktury dannyh: ucheb. posobie,Mvo obrazovanija i nauki RF, Gos. obrazovatel'noe uchrezhdenie vyssh. prof. obrazovanija “Penzenskij gos. unt” (PGU), Penza, (in Russian).
Рекомендованокпубликации:
ГоревымП. М.,кандидатомпедагогическихнаук, главнымредакторомжурнала«Концепт»
