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

1 Временная сложность алгоритма. Сравнительный анализ алгоритмов поиска.

Временная сложность (ВС) – зависимость времени выполнения алгоритма от количества обрабатываемых входных данных. Здесь представляет интерес среднее и худшее время выполнения алгоритма. ВС можно установить с различной точностью. Наиболее точной оценкой является аналитическое выражение для функции: t=t(N), где t – время, N – количество входных данных (размерность). Данная функция называется функцией временной сложности (ФВС).

Часто бывает достаточно определить лишь порядок функции временной сложности t(N).

Две функции f1(N) и f2(N) — одного порядка, если

Иначе это записывается в виде: f1(N)=О(f2(N)) (Читается " О большое "). Фраза «сложность алгоритма» есть О(n!)» означает, что с увеличением параметра n, характеризующего количество входной информации алгоритма, время работы алгоритма не может быть ограничено величиной, которая растет медленнее, чем n!;

По временной сложности все задачи классифицируются следующим образом:

1 класс. Задачи класса Р - это задачи, для которых известен алгоритм и временная сложность оценивается полиномиальной функцией f(N) = ak*N+ak-1*N2+…+a0*Nk+1. Алгоритмы таких задач называют также "хорошими" алгоритмами. Этих алгоритмов мало, они образуют небольшой по мощности класс. Легко реализуются. Функция временной сложности для таких алгоритмов имеет вид O(Nk). Класс Р вмещает все те проблемы, решение которых считается «быстрым», то есть полиномиально зависящим от размера входа. Сюда относится сортировка, поиск во множестве и многие другие.

2 класс. Задачи класса Е - это задачи, для которых алгоритм известен, но сложность таких алгоритмов O(fn), где f - константа. Задачи такого класса - это задачи построения всех подмножеств некоторого множества, задачи построения всех полных подграфов графа. При небольших N экспоненциальный алгоритм может работать быстрее полиномиального.

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

Алгоритмы поиска в неупорядоченных массивах Алгоритм линейного поиска

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

Алгоритм быстрого линейного поиска

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

Определим среднее число шагов при поиске элементов в массиве из N элементов. Для этого подсчитаем суммарное число шагов S при поиске каждого элемента массива. Исходя из алгоритма, не более чем N/2 элементов ищется за log2N шагов,N/4 элементов – за (log2N)-1 шагов, и

т.д. Отсюда S=((N/2)*log2N)+((N/4)*((log2N)-1)+…+1.

Среднее число шагов равно S/N, что составляет O(log2N).

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

3.Алгоритм блочного поиска

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

Анализ алгоритма блочного поиска

Пусть массив состоит из N элементов и при поиске разбивается на X равных блоков. Тогда в каждом блоке будет не более N/X элементов. В худшем случае, если искомый элемент окажется в последнем блоке, то для поиска блока потребуется просмотреть X элементов массива. Выполнить линейный поиск в блоке можно, просмотрев не более чем N/X элементов. Следовательно, общее число обрабатываемых элементов не превышает X+N/X. При таком разбиении массива на блоки в худшем случае понадобиться обработать не более чем 2*√ Nэлементов массива, а в среднем - √ элементов.

2 Базовые и улучшенные сортировки на основе выбора, включения и обмена. Их

сравнительный анализ.

Формулировка задачи может быть записана следующим образом.

Если даны элементы а1, а2 ,…, аn, то сортировка означает перестановку этих элементов в массив ак1, ак2,…,акn, где при заданной функции упорядочения f справедливы отношения f(ак1)<=f(ак2)<= …<=f(акn). Обычно функция упорядочения f не вычисляется по какому-то специальному правилу, а является значением элемента.

Метод сортировки называется устойчивым, если относительный порядок элементов с одинаковыми значениями не меняется при сортировке; неустойчивым – в противном случае.

Методы сортировки, в зависимости от лежащего в их основе приема, можно разбить на три базовых класса:

1)сортировка вставками;

2)сортировка выбором;

3)сортировка обменом.

Сортировка вставками

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

Алгоритм сортировки вставками

1.Запоминаем элемент, подлежащий вставке.

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

3.Вставляем элемент на освободившееся место. Пункты 1-3 выполняем для всех элементов массива, кроме первого.

При поиске подходящего места для элемента x удобно чередовать сравнения и пересылки, т. е. как бы "просеивать"x, сравнивая его с очередным элементом m[j] и либо вставляя x, либо пересылая m[j] вправо. Просеивание может быть закончено при двух различных условиях:

1)найден элемент аi с ключом меньшим, чем ключ x,

2)достигнут левый конец готовой последовательности.

Пример, товарищи!

Анализ сортировки вставками

Если первоначальный массив отсортирован, то на каждом просмотре делается только одно сравнение, так что эта сортировка имеет порядок O(N). Если массив первоначально отсортирован в обратном порядке, то данная сортировка имеет порядок O(N2), поскольку общее число сравнений равно