Классика алгоритмизации

Размещено на http://www.allbest.ru/

Санкт-Петербургский политехнический университет Петра Великого

Институт компьютерных наук и технологий

Кафедра «Компьютерные интеллектуальные технологии»

КУРСОВАЯ РАБОТА

Классика алгоритмизации

по дисциплине «Информатика»

Выполнил студент гр. 1 В.В. Ефимов

Руководитель, доцент, к.н. Е.Г. Крылова

«__» _______ 201__ г

Санкт-Петербург

201__



ВВЕДЕНИЕ

Работа посвящена основам теории алгоритмов, в частности, одному из её основных понятий - оценке эффективности того или иного алгоритма. Сперва будет дано формальное определение понятия временной эффективности, которое позже будет проиллюстрировано на примере алгоритмов сортировок.

Цель работы - тщательно изучить и формализовать понятие «эффективности алгоритма», а также рассмотреть одну из фундаментальных задач при изучении алгоритмов - задачу сортировки.



1. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ

1.1 Понятие алгоритма

Алгоритм -- набор инструкций, описывающих порядок действий исполнителя для достижения результата решения задачи за конечное число действий, при любом наборе исходных данных.

Говоря неформально, алгоритм - это любая корректно определенная вычислительная процедура, на вход которой подается некоторая величина или набор величин и результатом выполнения которой является выходная величина или набор значений.

Алгоритм можно рассматривать как инструмент, предназначенный для решения корректно поставленной вычислительной задачи. В постановке задачи в общих чертах задаются отношения между входом и выходом. В алгоритме описывается конкретная вычислительная процедура, с помощью которой удается добиться выполнения указанных отношений.

Говорят, что алгоритм корректен, если для любых входных данных результатом его работы являются корректные выходные данные. Мы говорим, что корректный решает данную вычислительную задачу. Если алгоритм некорректный, то для некоторых вводов он вообще может не завершить свою работу ил выдать неправильный ответ.

Алгоритм может быть задан на естественном языке, в виде компьютерной программы или даже воплощен в аппаратном обеспечении. Единственной требование - его спецификация должна предоставлять точное описание вычислительной процедуры, которую требуется выполнить.

1.2 Эффективность алгоритма

Различные алгоритмы, разработанные для решения одной и той же задачи, часто очень сильно отличаются по эффективности. Эти различия могут быть намного значительнее тех, которые вызваны применением неодинакового аппаратного и программного обеспечения. Проявляются они прежде всего в плане расходов времени.

В общем случае время работы алгоритма увеличивается с увеличением количества входных данных, поэтому общепринятая практика - представлять время работы как функцию, зависящую от количества входных элементов.

Наиболее адекватное понятие размера входных данных зависит от рассматриваемой задачи. Во многих задачах, таких как сортировка или дискретные преобразования Фурье, это количество входных элементов, например, размер n сортируемого массива. Для многих других задач, таких как перемножение двух целых чисел, наиболее подходящая мера размера ввода - количество битов, необходимых для представления входных данных в двоичных обозначениях.

Время работы алгоритма для тех или иных входных данных измеряется в количестве элементарных операций, или шагов, которые необходимо выполнить. Можно исходить из точки зрения, согласно которой для выполнения каждого шага требуется фиксированное время, тогда время работы алгоритма - это сумма промежутков времени, необходимых для выполнения каждой входящей в его состав выполняемой инструкции.

Необходимо заметить, что даже если размер входных данных является фиксированной величиной, время работы алгоритма может зависеть от самих входных данных. В примере сортировки массива время зависит от степени упорядоченности сортируемых величин, которой они обладали до ввода. Очевидно, что самый благоприятный случай - это когда все элементы массива уже отсортированы, а наихудший - когда массив находится в порядке, обратном требуемому. Далее основное внимание будет уделено времени работы в наихудшем случае, т.е. максимальному времени работы для любых входных данных размером n. На то есть три причины:

1. Время работы алгоритма в наихудшем случае - это верхний предел этой величины для любых входных данных.

2. В некоторых алгоритмах наихудший случай встречается довольно часто.

3. Характер поведения усредненного времени ничем не лучше поведения работы для наихудшего случая.

1.2.1 Порядок роста

Теперь введем ещё одно абстрактное понятие, упрощающее анализ алгоритма. Это порядок роста интересующего нас времени работы.

Допустим, что время работы описывается формулой где a, b и c - некоторые константы. Во внимание будет приниматься только главный член формулы (), поскольку при больших значениях n членами меньшего порядка можно пренебречь. Кроме того, постоянный множитель при главном члене будет также будет игнорироваться, так как для оценки вычислительной эффективности со входными данными большого объема они менее важны, чем порядок роста. Таким образом, время работы алгоритма равно и( (произносится “тета от n в квадрате”).

Обычно один алгоритм рассматривается как более эффективный по сравнению с другим, если время его работы в наихудшем случае имеет более низкий порядок роста.

1.2.2 Асимптотические обозначения

Обозначение и( можно строго определить, сделав таким образом понятие порядка роста более формализованным. Мы говорим, что , имеет порядок роста и(), если существуют положительные постоянные и независимые от n, такие, что

для всякого достаточно большого n.

На рисунке показано интуитивное изображение функций , таких, что

).

Для всех значений n, лежащих справа от n0, функция больше или равна функции , но не превосходит функцию . Другими словами, для всех функция равна функции с точностью до постоянного множителя. Говорят, что функция является асимптотически точной оценкой функции

Интуитивно понятно, что при асимптотически точной оценке положительных функций, слагаемыми низших порядков в них можно пренебречь, поскольку при больших n они становятся несущественными. При больших n даже небольшой доли старшего слагаемого достаточно для того, чтобы превзойти слагаемые низших порядков.

В -обозначениях функция асимптотически ограничивается сверху и снизу. Если же достаточно определить только асимптотическую верхнюю границу, используются O-обозначения. Для данной функции обозначение О( означает, что существуют положительные постоянные c и , такие, что

для всех .

O-обозначения применяются, когда нужно указать верхнюю границу функции с точностью до постоянного множителя.

1.2.3 Другие оценки эффективности алгоритма

Степень роста наихудшего времени выполнения -- не единственный критерий оценки алгоритмов и программ. Приведем несколько соображений, позволяющих посмотреть на критерий времени выполнения с других точек зрения.

1. Если создаваемая программа будет использована только несколько раз, тогда стоимость написания и отладки программы будет доминировать в общей стоимости программы, т.е. фактическое время выполнения не окажет существенного влияния на общую стоимость. В этом случае следует предпочесть алгоритм, наиболее простой для реализации.

2. Если программа будет работать только с "малыми" входными данными, то степень роста времени выполнения будет иметь меньшее значение, чем константа, присутствующая в формуле времени выполнения. Вместе с тем и понятие "малости" входных данных зависит от точного времени выполнения конкурирующих алгоритмов. Существуют алгоритмы, такие как алгоритм целочисленного умножения, асимптотически самые эффективные, но которые никогда не используют на практике даже для больших задач, так как их константы пропорциональности значительно превосходят подобные константы других, более простых и менее "эффективных" алгоритмов.

3. Эффективные, но сложные алгоритмы могут быть нежелательными, если готовые программы будут поддерживать лица, не участвующие в написании этих программ. Будем надеяться, что принципиальные моменты технологии создания эффективных алгоритмов широко известны, и достаточно сложные алгоритмы свободно применяются на практике. Однако необходимо предусмотреть возможность того, что эффективные, но "хитрые" алгоритмы не будут востребованы из-за их сложности и трудностей, возникающих при попытке в них разобраться.

4. Известно несколько примеров, когда эффективные алгоритмы требуют таких больших объемов машинной памяти (без возможности использования более медленных внешних средств хранения), что этот фактор сводит на нет преимущество "эффективности" алгоритма.

5. В численных алгоритмах точность и устойчивость алгоритмов не менее важны, чем их временная эффективность.



2. АЛГОРИТМЫ СОРТИРОВКИ

2.1 Постановка общей задачи сортировки

Вход. Последовательность из n чисел

Выход. Перестановка (переупорядочивание) входной последовательности, такая, что

Входная последовательность обычно имеет вид n-элементного массива, хотя может иметь и другое представление, например, в виде связанного списка.

2.2 Структура данных

На практике сортируемы числа редко являются изолированными значениями. Обычно каждое из них входит в состав набора данных, который называется записью. В каждой записи содержится ключ, представляющий собой сортируемое значение, в то время как остальная часть записи состоит из сопутствующих данных, дополняющих ключ. Алгоритм сортировки на практике должен быть реализован так, чтобы он вместе с ключами переставлял и сопутствующие данные. Если каждая запись включает в себя сопутствующие данные большого объема, то с целью свести к минимуму перемещение данных сортировка часто проводится не в исходном массиве, а в массиве указателей на записи.

Это замечание относится к особенностям реализации, отличающим алгоритм от конечной программы. Алгоритм описывает метод определения порядка сортировки вне зависимости от того, сортируются ли отдельные числа или большие записи с многобайтовыми сопутствующими данными. Таким образом, если речь идет о задаче сортировки, обычно предполагается, что входные данные состоят только из чисел. Преобразование алгоритма, сортирующего числа, в программу для сортировки записей не представляет концептуальных трудностей, хотя и не лишено некоторых нюансов.

2.3 Фундаментальность задачи

Многие ученые в области вычислительной техники рассматривают эту задачу как наиболее фундаментальную при изучении алгоритмов. Тому есть несколько причин:

1. Часто в алгоритмах сортировка используется в качестве ключевой подпрограммы.

2. Имеется большой выбор алгоритмов сортировки, в которых применяются самые разные технологии. Фактически в алгоритмах сортировки используются многие важные методы, применяемые при разработке различных классов алгоритмов. В этом отношении задача сортировки представляет также исторический интерес.

3. В процессе реализации алгоритмов сортировки на передний план выходят многие прикладные проблемы. Выбор наиболее производительной программы сортировки зависит от многих факторов, многие из которых лучше решать на уровне алгоритма, а не настройкой кода.

2.4 Пирамидальная сортировка

Сортировка пирамидой использует бинарное сортирующее дерево. Сортирующее дерево -- это такое дерево, у которого выполнены условия:

1. Каждый лист имеет глубину либо , либо , -- максимальная глубина дерева.

2. Значение в любой вершине не меньше (другой вариант -- не больше) значения её потомков.

Удобная структура данных для сортирующего дерева -- такой массив Array, что Array[1] -- элемент в корне, а потомки элемента Array[i] являются Array[2i] и Array[2i+1].

Алгоритм сортировки будет состоять из двух основных шагов:

1. Выстраиваем элементы массива в виде сортирующего дерева

2. Будем удалять элементы из корня по одному за раз и перестраивать дерево. То есть на первом шаге обмениваем Array[1] и Array[n], преобразовываем Array[1], Array[2], …, Array[n-1] в сортирующее дерево. Затем переставляем Array[1] и Array[n-1], преобразовываем Array[1], Array[2], …, Array[n-2] в сортирующее дерево. Процесс продолжается до тех пор, пока в сортирующем дереве не останется один элемент.

Рассчитаем быстродействие построения сортирующего дерева в самом плохом случае. Пусть массив уже отсортирован по возрастанию, и каждый добавляемый элемент вынужден просеиваться вверх до самого корня. Тогда при добавлении элемента номер i нам потребуется операций. Мы делаем эту процедуру для всех i от 0 до :

(1)

Оценим сумму в выражении (1) с помощью определённого интеграла:

(2)

Вычисляя интегралы, получаем:

(3)

Это означает, что затраченное время T(n) равно

(4)

Так как процедура сортировки дерева полностью аналогична построению дерева методом просеивания вверх, только производится «в обратном порядке»: пирамида не строится, а «разбирается» элемент-за-элементом, и элементы просеиваются не вверх, а вниз, то время работы алгоритма пирамидальной сортировки будет определяться аналогично формуле (4):

алгоритм сортировка эффективность

Пирамидальная сортировка была предложена Дж. Уильямсом в 1964 году.

Достоинства:

Имеет доказанную оценку худшего случая.

Не требует дополнительной памяти.

Недостатки:

Сложен в реализации.

На почти отсортированных массивах работает столь же долго, как и на хаотических данных.

2.5 Быстрая сортировка

Общая идея алгоритма состоит в следующем:

Выбрать из массива элемент, называемый опорным.

Сравнить все остальные элементы с опорным и переставить их в массиве так, чтобы разбить массив на три непрерывных отрезка, следующие друг за другом: «меньшие опорного», «равные» и «большие».

Для отрезков «меньших» и «больших» значений выполнить рекурсивно ту же последовательность операций, если длина отрезка больше единицы.

На практике массив обычно делят не на три, а на две части: например, «меньшие опорного» и «равные и большие»; такой подход в общем случае эффективнее, так как упрощает алгоритм разделения.

Время работы алгоритма быстрой сортировки зависит от степени сбалансированности разбиения. Сбалансированность, в свою очередь, зависит от того, какой элемент выбран в качестве опорного.

Наихудшее поведение алгоритма быстрой сортировки имеет место в случае, когда подпрограмма, выполняющая разбиение, порождает подзадачу с n-1 элементами, а вторую - пустую, то есть при каждом рекурсивном вызове больший массив будет на 1 короче, чем в предыдущий раз. Такое может произойти, если в качестве опорного на каждом этапе будет выбран элемент либо наименьший, либо наибольший из всех обрабатываемых. Предположим, что такое несбалансированное разбиение возникает при каждом рекурсивном вызове. Для выполнения разбиения требуется время и(n). Поскольку рекурсивный вызов процедуры разбиения, на вход которой подается массив размером 0 приводит к немедленному возврату из этой процедуры, то

T(0) = и(1).

Таким образом, общее время работы в худшем случае:

T(n)=T(n-1)+T(0)+и(n)=T(n-1)+и(n)

При суммировании промежутков времени, затрачиваемых на каждый уровень рекурсии, получается арифметическая прогрессия, что приводит к результату и(n^2).

В наилучшем же случае при каждой операции разделения массив делится на две почти одинаковые части, следовательно, максимальная глубина рекурсии, при которой размеры обрабатываемых подмассивов достигнут 1, составит log_2?n. В результате количество сравнений, совершаемых быстрой сортировкой, было бы равно значению рекурсивного выражения

T(n)=2T(n/2)+и(n),

что даёт общее время выполнения алгоритма

T(n)=n*log_2?n

Достоинства:

Один из самых быстродействующих алгоритмов сортировки общего назначения.

Прост в реализации.

Не требует большого количества дополнительной памяти

Недостатки:

Прямая реализация в виде функции с двумя рекурсивными вызовами может привести к ошибке переполнения стека.

2.6 Сортировка пузырьком

Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются n-1 раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает -- массив отсортирован. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим «наибольшим элементом», а наименьший элемент перемещается на одну позицию к началу массива («всплывает» до нужной позиции, как пузырёк в воде, отсюда и название алгоритма).

Имеет квадратичный порядок роста и(n^2).



ВЫВОДЫ

В процессе анализа приведенных алгоритмов мы убедились в том, что асимптотическая система оценки весьма удобна для получения общего представления о том, какой процесс будет порождать тот или иной алгоритм, и какие временные ресурсы он будет потреблять.

Так же была освещена общая задача сортировки информации и приведены конкретные способы её решения, которые можно резюмировать следующим образом:

1. Быстрая сортировка. Легко реализуема и наиболее оптимальна в плане затраченного времени, но требовательна к навыкам пользователя.

2. Пирамидальная сортировка. Сложна в реализации, но совсем не требует дополнительной памяти, а также относительно оптимальна в плане затраченного времени.

3. Пузырьковая сортировка не практична, но наиболее проста для понимания, используется в целях обучения.

Размещено на Allbest.ru

...