Алгоритмы и структуры данных. Сложность, сортировка, поиск

1. Сложность, сортировка, поиск

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

2. Введение

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

3. Сложность

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

4. Сложность

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

5. Классы оценок сложности

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

6. Класс P

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

7. Класс NP

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

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

8

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

9

10. Алгоритм поиска

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

11. Линейный (последовательный) поиск

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

12. Время выполнения

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

13. Пример реализации алгоритма линейного поиска на языке C++

template <class T>
int linear_search(const vector<T>& v, const T& item)
{
for (int i = 0; i < v.size(); i++)
{
if (v[i] == item)
{
return i; // элемент найден
}
}
return -1; // элемент не найден
}
13

14.

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

15. Двоичный (бинарный) поиск

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

16. Описание метода бинарного поиска

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

17. Описание метода бинарного поиска

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

18. Пример реализации алгоритма бинарного поиска на языке C++

template <class T>
int binary_search(const vector<T>& v, const T& item) {
int low = 0;
int high = v.size() - 1;
int mid;
while (low <= high) { // нахождение элемента-границы
mid = (low + high) / 2;
If (v[mid] < item) {
low = mid + 1;} // обращаемся выше элемента-границы
else if (v[mid] > item) {
high = mid - 1; // обращаемся ниже элемента-границы
}else { //элемент найден
return mid;}}
return -1; // элемент не найден
}
18

19. Время выполнения

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

20.

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

21. Алгоритм сортировки

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

22. Характеристики алгоритмов сортировки

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

23. Алгоритм сортировки подсчётом

-
алгоритм сортировки массива целых положительных
чисел, лежащих в определённом диапазоне. При
выполнении этого алгоритма подсчитывается число
элементов, меньших текущего элемента х, и число
одинаковых элементов, а затем выстраивается новый
массив, в который элемент х записывается сразу «на
свое место» (исходя из этих подсчётов)
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
24

25. Сложность

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

26.

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

27. Алгоритм сортировки выборкой

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

28. Иллюстрация выполнения алгоритма сортировки выборкой

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

29. Пример реализации алгоритма сортировки выборкой на языке C++

template <class T>
void selection_sort(vector<T>& 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;
}
}
}
29

30. Сложность алгоритма сортировки выборкой

На массиве из n элементов имеет
время выполнения в худшем, среднем и
лучшем случае O(n2), предполагая что
сравнения делаются за постоянное
время.
30

31. Алгоритм быстрой сортировки

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

32. Алгоритм быстрой сортировки

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

33. Сложность алгоритма быстрой сортировки

Лучший случай: O (n log n);
Промежуточный случай: O (n log n);
Худший случай: O (n2);

34.

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

35. Спасибо за внимание!

Москва, 2008
35