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

Август 1, 2022

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

Содержание

2. Введение Теория сложности вычислений возникла из потребности сравнивать быстродействие алгоритмов (например, алгоритмов поиска и сортировки), чётко
3. Сложность мера использования алгоритмом ресурсов времени или пространства. Время выполнения алгоритма определяется количеством тривиальных шагов, необходимых
4. Сложность F (n) – функция трудоемкости, определяющая зависимость между входными данными и кол-вом базовых операций (
5. Классы оценок сложности множества вычислительных проблем, для решения которых известны алгоритмы, схожие по сложности O(1) –
6. Класс P Проблемы, решение которых считается «быстрым», то есть полиноминально зависящим от размера входных данных (например,
7. Класс NP Проблемы, для решения которых используются лишь алгоритмы, экспоненциально зависящие от размера входных данных (например,
8. Время выполнения алгоритма для небольших n
9. Время выполнения алгоритма для больших n
10. Алгоритм поиска - алгоритм нахождения заданного значения произвольной функции в некотором наборе значений Виды поиска Линейный
11. Линейный (последовательный) поиск - простейший вид поиска заданного элемента на некотором отрезке (множестве), осуществляемый путем последовательного
12. Время выполнения Если отрезок имеет длину n, то найти решение с точностью до ε можно за
13. Пример реализации алгоритма линейного поиска на языке C++ template int linear_search(const vector & v, const T&
14. За: Не требует сортировки значений множества Не требует дополнительного анализа функции. Не требует дополнительной памяти. =>
15. Двоичный (бинарный) поиск - поиск заданного элемента на упорядоченном множестве, осуществляемый путем неоднократного деления этого множества
16. Описание метода бинарного поиска Упорядоченное по возрастанию множество элементов, необходимо найти элемент с значением, равным 9
17. Описание метода бинарного поиска Сравнение элемента-границы с искомым элементом: 9 В левой части повторяем алгоритм до
18. Пример реализации алгоритма бинарного поиска на языке C++ template int binary_search(const vector & v, const T&
19. Время выполнения Когда функция имеет вещественный аргумент, найти решение с точностью до ε можно за время
20. За: Относительная быстрота выполнения поиска (по линейным) Против: Бинарный поиск может применяться только на упорядоченном множестве
21. Алгоритм сортировки - алгоритм для упорядочения элементов в списке. В случае, когда элемент списка имеет несколько
22. Характеристики алгоритмов сортировки Устойчивость – изменение относительного положения равных элементов Естественность поведения – улучшение работы алгоритма
23. Алгоритм сортировки подсчётом алгоритм сортировки массива целых положительных чисел, лежащих в определённом диапазоне. При выполнении этого
24. Схема реализации сортировки подсчётом // A[1..n] – входной массив, B[1..n] – выходной, C[1..k] - // вспомогательный,
25. Сложность Циклы в строках 1-2 и 6-7 работают за время O(k), Циклы в строках 3-4 и
26. За: Устойчивая сортировка: если во входном массиве присутствуют несколько одинаковых чисел, то в выходном массиве они
27. Алгоритм сортировки выборкой - неустойчивый алгоритм сортировки, при котором выбирается минимальное значение, производится обмен этого значения
28. Иллюстрация выполнения алгоритма сортировки выборкой 1.Начальный массив 2.Минимальный элемент = 12 3. Минимальный элемент = 7
29. Пример реализации алгоритма сортировки выборкой на языке C++ template void selection_sort(vector & v) { for (int
30. Сложность алгоритма сортировки выборкой На массиве из n элементов имеет время выполнения в худшем, среднем и
31. Алгоритм быстрой сортировки алгоритм сортировки списка (множества, массива), основанный на принципе «разделяй и властвуй», самый быстрый
32. Алгоритм быстрой сортировки Выбираем в массиве некоторый элемент, который будем называть опорным элементом; Разделяем массив таким
33. Сложность алгоритма быстрой сортировки Лучший случай: O (n log n); Промежуточный случай: O (n log n);
34. Достоинства: Самый быстродействующий из всех существующих неспециализированных алгоритмов обменной сортировки; Простая реализация; Хорошо сочетается с алгоритмами
36. Скачать презентацию

Слайд 2

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

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

Слайд 3

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

тривиальных шагов, необходимых для решения проблемы и зависит от размера входных данных (далее n)

Пространство объёмом памяти или места на носителе данных, используемом алгоритмом.

Слайд 4

Сложность
F (n) – функция трудоемкости, определяющая зависимость между входными данными и

кол-вом базовых операций ( временными затратами алгоритма )

O(g(n)) = { F(n): существуют положительные константы c и n0 такие, что 0≤ f(n) ≤ cg(n) для всех n≥ n0}

Асимптотическая оценка

Слайд 5

Классы оценок сложности
множества вычислительных проблем, для решения которых известны алгоритмы, схожие

по сложности

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

Слайд 6

Класс P
Проблемы, решение которых считается «быстрым», то есть полиноминально зависящим от

размера входных данных (например, O(n), O(n2))

Сортировка
Поиск во множестве
Выяснение связности графов

Примеры

Слайд 7

Класс NP
Проблемы, для решения которых используются лишь алгоритмы, экспоненциально зависящие от

размера входных данных (например, O(2n))

Задача коммивояжера
Задача выполнимости булевых формул
факторизация

Примеры

Слайд 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

Описание метода бинарного поиска
Упорядоченное по возрастанию множество элементов, необходимо найти элемент

с значением, равным 9

Выбор середины вектора – элемента-границы

Слайд 17

Описание метода бинарного поиска
Сравнение элемента-границы с искомым элементом: 9 < 21,

отбрасываем правую часть

В левой части повторяем алгоритм до тех пор, пока элемент-граница не равен 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 <= 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; // элемент не найден
}

Слайд 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 и 10-11 - за время O(n),
Значит, весь алгоритм работает за время O(n+k); если k= O(n), то время работы (временная сложность) есть O(n)

Слайд 26

За:
Устойчивая сортировка: если во входном массиве присутствуют несколько одинаковых чисел, то

в выходном массиве они стоят в том же порядке, что и во входном

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

Слайд 27

Алгоритм сортировки выборкой
- неустойчивый алгоритм сортировки, при котором выбирается минимальное

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

Слайд 28

Иллюстрация выполнения алгоритма сортировки выборкой
1.Начальный массив
2.Минимальный элемент = 12
3. Минимальный элемент

= 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(n2), предполагая что сравнения делаются за постоянное время.

Слайд 31

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

и властвуй», самый быстрый из известных универсальных алгоритмов сортировки.

Слайд 32

Алгоритм быстрой сортировки
Выбираем в массиве некоторый элемент, который будем называть опорным

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

Слайд 33

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

(n log n);
Худший случай: O (n2);

Слайд 34

Достоинства:
Самый быстродействующий из всех существующих неспециализированных алгоритмов обменной сортировки;
Простая реализация;
Хорошо сочетается

с алгоритмами кэширования и подкачки памяти;
Хорошо работает на «почти отсортированных» (естественность поведения)

Недостатки:
При классической реализации требует в худшем случае много дополнительной памяти;
Неустойчив — если требуется устойчивость, приходится расширять ключ.

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

Содержание

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

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

Сложность F (n) – функция трудоемкости, определяющая зависимость между входными данными и

Классы оценок сложностимножества вычислительных проблем, для решения которых известны алгоритмы, схожие

Класс PПроблемы, решение которых считается «быстрым», то есть полиноминально зависящим от

Класс NPПроблемы, для решения которых используются лишь алгоритмы, экспоненциально зависящие от

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

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

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

Линейный (последовательный) поиск- простейший вид поиска заданного элемента на некотором отрезке

Время выполненияЕсли отрезок имеет длину n, то найти решение с точностью

Пример реализации алгоритма линейного поиска на языке C++template int linear_search(const

За:Не требует сортировки значений множестваНе требует дополнительного анализа функции. Не требует

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

Описание метода бинарного поискаУпорядоченное по возрастанию множество элементов, необходимо найти элемент

Описание метода бинарного поискаСравнение элемента-границы с искомым элементом: 9 < 21,

Пример реализации алгоритма бинарного поиска на языке C++template int binary_search(const

Время выполненияКогда функция имеет вещественный аргумент, найти решение с точностью до

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

Алгоритм сортировки- алгоритм для упорядочения элементов в списке. В случае, когда

Характеристики алгоритмов сортировкиУстойчивость – изменение относительного положения равных элементовЕстественность поведения –

Алгоритм сортировки подсчётомалгоритм сортировки массива целых положительных чисел, лежащих в определённом

Схема реализации сортировки подсчётом// A[1..n] – входной массив, B[1..n] – выходной,

СложностьЦиклы в строках 1-2 и 6-7 работают за время O(k),Циклы в

За:Устойчивая сортировка: если во входном массиве присутствуют несколько одинаковых чисел, то

Алгоритм сортировки выборкой- неустойчивый алгоритм сортировки, при котором выбирается минимальное

Иллюстрация выполнения алгоритма сортировки выборкой1.Начальный массив2.Минимальный элемент = 123. Минимальный элемент

Пример реализации алгоритма сортировки выборкой на языке C++template void selection_sort(vector&

Сложность алгоритма сортировки выборкойНа массиве из n элементов имеет время выполнения

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

Алгоритм быстрой сортировкиВыбираем в массиве некоторый элемент, который будем называть опорным

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

Достоинства:Самый быстродействующий из всех существующих неспециализированных алгоритмов обменной сортировки;Простая реализация;Хорошо сочетается

Похожие презентации