Разделы презентаций
- Разное
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Сложность, сортировка, поиск
Содержание
- 1. Сложность, сортировка, поиск
- 2. Введение Теория сложности вычислений возникла из
- 3. Сложностьмера использования алгоритмом ресурсов времени или пространства.Время
- 4. Сложность F (n) – функция трудоемкости, определяющая зависимость
- 5. Классы оценок сложностимножества вычислительных проблем, для решения
- 6. Класс PПроблемы, решение которых считается «быстрым», то
- 7. Класс NPПроблемы, для решения которых используются лишь
- 8. Время выполнения алгоритма для небольших n
- 9. Время выполнения алгоритма для больших n
- 10. Алгоритм поиска- алгоритм нахождения заданного значения произвольной
- 11. Линейный (последовательный) поиск- простейший вид поиска заданного
- 12. Время выполненияЕсли отрезок имеет длину n, то
- 13. Пример реализации алгоритма линейного поиска на языке
- 14. За:Не требует сортировки значений множестваНе требует дополнительного
- 15. Двоичный (бинарный) поиск- поиск заданного элемента на
- 16. Описание метода бинарного поискаУпорядоченное по возрастанию множество
- 17. Описание метода бинарного поискаСравнение элемента-границы с искомым
- 18. Пример реализации алгоритма бинарного поиска на языке
- 19. Время выполненияКогда функция имеет вещественный аргумент, найти
- 20. За:Относительная быстрота выполнения поиска (по линейным)Против:Бинарный поиск может применяться только на упорядоченном множестве
- 21. Алгоритм сортировки- алгоритм для упорядочения элементов в
- 22. Характеристики алгоритмов сортировкиУстойчивость – изменение относительного положения
- 23. Алгоритм сортировки подсчётомалгоритм сортировки массива целых положительных
- 24. Схема реализации сортировки подсчётом// A[1..n] –
- 25. СложностьЦиклы в строках 1-2 и 6-7 работают
- 26. За:Устойчивая сортировка: если во входном массиве присутствуют
- 27. Алгоритм сортировки выборкой- неустойчивый алгоритм сортировки,
- 28. Иллюстрация выполнения алгоритма сортировки выборкой1.Начальный массив2.Минимальный элемент
- 29. Пример реализации алгоритма сортировки выборкой на языке
- 30. Сложность алгоритма сортировки выборкойНа массиве из n
- 31. Алгоритм быстрой сортировкиалгоритм сортировки списка (множества, массива),
- 32. Алгоритм быстрой сортировкиВыбираем в массиве некоторый элемент,
- 33. Сложность алгоритма быстрой сортировкиЛучший случай: O (n
- 34. Достоинства:Самый быстродействующий из всех существующих неспециализированных алгоритмов
- 35. Спасибо за внимание!Москва, 2008
- 36. Скачать презентанцию
Введение Теория сложности вычислений возникла из потребности сравнивать быстродействие алгоритмов (например, алгоритмов поиска и сортировки), чётко описывать их поведение (время исполнения и объём необходимой памяти) в зависимости от размера входа.
Слайды и текст этой презентации
Слайд 1Сложность, сортировка, поиск
Работа по дисциплине «Алгоритмы и структуры данных»
Выполнена
Садукевич А.В.,
271ПИ
Слайд 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))
Задача коммивояжера
Задача выполнимости булевых
формулфакторизация
Примеры
Слайд 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- максимальное число элементов
в массиве Afor 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
![Схема реализации сортировки подсчётом// A[1..n] – входной массив, B[1..n] – выходной, C[1..k] -// вспомогательный, k-](/img/tmb/7/631280/2877fdedde611260e8896d28e644b84b-800x.jpg "Сложность, сортировка, поиск Схема реализации сортировки подсчётом// A[1..n] – входной массив, B[1..n] – выходной,")
Слайд 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 Достоинства:
Самый быстродействующий из всех существующих неспециализированных алгоритмов обменной сортировки;
Простая реализация;
Хорошо
сочетается с алгоритмами кэширования и подкачки памяти;
Хорошо работает на «почти
отсортированных» (естественность поведения) Недостатки:
При классической реализации требует в худшем случае много дополнительной памяти;
Неустойчив — если требуется устойчивость, приходится расширять ключ.
