1 Сложность, сортировка, поиск Работа по дисциплине «Алгоритмы и структуры данных» Выполнена Садукевич А.В., 271ПИ

Введение Теория сложности вычислений возникла из потребности сравнивать быстродействие алгоритмов (например, алгоритмов поиска и сортировки), чётко описывать их поведение (время исполнения и объём необходимой памяти) в зависимости от размера входа.

3 Сложность - мера использования алгоритмом ресурсов времени или пространства. Время выполнения алгоритма определяется количеством тривиальных шагов, необходимых для решения проблемы и зависит от размера входных данных (далее n) Пространство объёмом памяти или места на носителе данных, используемом алгоритмом.

4 Сложность F (n) – функция трудоемкости, определяющая зависимость между входными данными и кол-вом базовых операций ( временными затратами алгоритма ) O(g(n)) = { F(n): существуют положительные константы c и n 0 такие, что 0 f(n) cg(n) для всех n n 0 } Асимптотическая оценка

5 Классы оценок сложности - множества вычислительных проблем, для решения которых известны алгоритмы, схожие по сложности O(1) – постоянное время O(log(n)) – логарифмическое время O(n) – линейное время O(n log(n)) – "n-log-n" время O(n 2 ) – квадратичное время O(n 3 ) – кубическое время O(2 n ) – экспоненциальное время

6 Класс P Проблемы, решение которых считается «быстрым», то есть полиноминально зависящим от размера входных данных (например, O(n), O(n 2 )) Сортировка Поиск во множестве Выяснение связности графов Примеры

7 Класс NP Проблемы, для решения которых используются лишь алгоритмы, экспоненциально зависящие от размера входных данных (например, O(2 n )) Задача коммивояжера Задача выполнимости булевых формул факторизация Примеры

8 Время выполнения алгоритма для небольших n

9 Время выполнения алгоритма для больших n

10 Алгоритм поиска - алгоритм нахождения заданного значения произвольной функции в некотором наборе значений Виды поиска Линейный поиск (последовательный поиск, поиск за линейное время) Двоичный (бинарный) поиск

11 Линейный (последовательный) поиск - простейший вид поиска заданного элемента на некотором отрезке (множестве), осуществляемый путем последовательного сравнения очередного рассматриваемого значения с искомым до тех пор, пока эти значения не совпадут

12 Время выполнения Если отрезок имеет длину n, то найти решение с точностью до ε можно за время n/ ε Сложность линейного поиска O(n) Сложность

13 Пример реализации алгоритма линейного поиска на языке C++ template int linear_search(const vector & v, const T& item) { for (int i = 0; i < v.size(); i++) { if (v[i] == item) { return i; // элемент найден } return -1; // элемент не найден }

14 За: Не требует сортировки значений множества Не требует дополнительного анализа функции. Не требует дополнительной памяти. => Следовательно, может работать в потоковом режиме при непосредственном получении данных из любого источника. Против: Малоэффективен по сравнению с другими алгоритмами поиска. =>Следовательно, используется, если множество содержит небольшое количество элементов

15 Двоичный (бинарный) поиск - поиск заданного элемента на упорядоченном множестве, осуществляемый путем неоднократного деления этого множества на две части таким образом, что искомый элемент попадает в одну из этих частей. Поиск заканчивается при совпадении искомого элемента с элементом- границей между частями множества или при отсутствии искомого элемента.

16 Описание метода бинарного поиска 1. Упорядоченное по возрастанию множество элементов, необходимо найти элемент с значением, равным 9 2. Выбор середины вектора – элемента- границы

17 Описание метода бинарного поиска 3. Сравнение элемента-границы с искомым элементом: 9 < 21, отбрасываем правую часть 4. В левой части повторяем алгоритм до тех пор, пока элемент-граница не равен 9

18 Пример реализации алгоритма бинарного поиска на языке C++ template int binary_search(const vector & v, const T& item) { int low = 0; int high = v.size() - 1; int mid; while (low item) { high = mid - 1; // обращаемся ниже элемента-границы }else { //элемент найден return mid;}} return -1; // элемент не найден }

19 Время выполнения Когда функция имеет вещественный аргумент, найти решение с точностью до ε можно за время (log a), где a=1/ε. Когда аргумент дискретен, и изначально лежит на отрезке длины n, поиск решения займёт (1+ log n) времени Сложность бинарного поиска O( log n) Сложность

20 За: Относительная быстрота выполнения поиска (по линейным) Против: Бинарный поиск может применяться только на упорядоченном множестве

21 Алгоритм сортировки - алгоритм для упорядочения элементов в списке. В случае, когда элемент списка имеет несколько полей, поле, служащее критерием порядка, называется ключом сортировки. Остальные поля могут в ней не участвовать.

22 Характеристики алгоритмов сортировки Устойчивость – изменение относительного положения равных элементов Естественность поведения – улучшение работы алгоритма при улучшении (частичной или полной сортировке) входных данных Сравнения - количество операций сравнения элементов Перестановки - количество перестановок элементов

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

24 Схема реализации сортировки подсчётом // A[1..n] – входной массив, B[1..n] – выходной, C[1..k] - // вспомогательный, k- максимальное число элементов в массиве A for i := 1 to k do C[i] := 0 for j :=1 to length[A] do C[A[j]] := C[A[j]]+ 1 C[i] равно количеству элементов, равных i for i := 2 to k do C[i] := C[i] + C[i -1] C[i] равно количеству элементов, не превосходящих i for j := length[A] downto 1 do B[C[A[j]]] := A[j] C[A[j]] := C[A[j]]-1

25 Сложность Циклы в строках 1-2 и 6-7 работают за время O(k), Циклы в строках 3-4 и за время O(n), Значит, весь алгоритм работает за время O(n+k); если k= O(n), то время работы (временная сложность) есть O(n)

26 За: Устойчивая сортировка: если во входном массиве присутствуют несколько одинаковых чисел, то в выходном массиве они стоят в том же порядке, что и во входном Против: Ограничения, налагаемые на входные данные (массив целых положительных чисел в известном диапазоне)

27 Алгоритм сортировки выборкой - неустойчивый алгоритм сортировки, при котором выбирается минимальное значение, производится обмен этого значения со значением на первой позиции в списке (массиве, множестве). Эти операции повторяются с хвостом списка: исключаются уже отсортированные элементы – до тех пор, пока весь список не будет отсортирован.

28 Иллюстрация выполнения алгоритма сортировки выборкой 1.Начальный массив 2.Минимальный элемент = Минимальный элемент = 7 4…. Минимальный элемент = 3 Затем повторяются те же шаги без учёта отсортированного элемента 5. Итог – отсортированный массив

29 Пример реализации алгоритма сортировки выборкой на языке C++ template void selection_sort(vector & v) { for (int i = 0; i < v.size() - 1; i++) { int best = i; for (int j = i + 1; j < v.size(); j++) { if (v[j] < v[best]) { best = j; } if (best != i) { T temp = v[i]; v[i] = v[best]; v[best] = temp; }

30 Сложность алгоритма сортировки выборкой На массиве из n элементов имеет время выполнения в худшем, среднем и лучшем случае O(n 2 ), предполагая что сравнения делаются за постоянное время.

Алгоритм быстрой сортировки - алгоритм сортировки списка (множества, массива), основанный на принципе «разделяй и властвуй», самый быстрый из известных универсальных алгоритмов сортировки.

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

Сложность алгоритма быстрой сортировки Лучший случай: O (n log n); Промежуточный случай: O (n log n); Худший случай: O (n 2 );

Достоинства: Самый быстродействующий из всех существующих неспециализированных алгоритмов обменной сортировки; Простая реализация; Хорошо сочетается с алгоритмами кэширования и подкачки памяти; Хорошо работает на «почти отсортированных» (естественность поведения) Недостатки: При классической реализации требует в худшем случае много дополнительной памяти; Неустойчив если требуется устойчивость, приходится расширять ключ.

35 Спасибо за внимание! Москва, 2008