Поисковые системы
<<  Поисковые системы Поиск и сортировка  >>
Сложность, сортировка, поиск
Сложность, сортировка, поиск
Введение
Введение
Сложность
Сложность
Сложность
Сложность
Классы оценок сложности
Классы оценок сложности
Примеры
Примеры
Примеры
Примеры
Время выполнения алгоритма для небольших n
Время выполнения алгоритма для небольших n
Время выполнения алгоритма для больших n
Время выполнения алгоритма для больших n
Алгоритм поиска
Алгоритм поиска
Линейный (последовательный) поиск
Линейный (последовательный) поиск
Время выполнения
Время выполнения
Пример реализации алгоритма линейного поиска на языке C++
Пример реализации алгоритма линейного поиска на языке C++
За: Не требует сортировки значений множества Не требует
За: Не требует сортировки значений множества Не требует
Двоичный (бинарный) поиск
Двоичный (бинарный) поиск
Описание метода бинарного поиска
Описание метода бинарного поиска
Описание метода бинарного поиска
Описание метода бинарного поиска
Пример реализации алгоритма бинарного поиска на языке C++
Пример реализации алгоритма бинарного поиска на языке C++
Время выполнения
Время выполнения
За: Относительная быстрота выполнения поиска (по линейным)
За: Относительная быстрота выполнения поиска (по линейным)
Алгоритм сортировки
Алгоритм сортировки
Характеристики алгоритмов сортировки
Характеристики алгоритмов сортировки
Алгоритм сортировки подсчётом
Алгоритм сортировки подсчётом
Схема реализации сортировки подсчётом
Схема реализации сортировки подсчётом
Сложность
Сложность
За: Устойчивая сортировка: если во входном массиве присутствуют
За: Устойчивая сортировка: если во входном массиве присутствуют
Алгоритм сортировки выборкой
Алгоритм сортировки выборкой
Иллюстрация выполнения алгоритма сортировки выборкой
Иллюстрация выполнения алгоритма сортировки выборкой
Пример реализации алгоритма сортировки выборкой на языке C++
Пример реализации алгоритма сортировки выборкой на языке C++
Сложность алгоритма сортировки выборкой
Сложность алгоритма сортировки выборкой
Алгоритм быстрой сортировки
Алгоритм быстрой сортировки
Алгоритм быстрой сортировки
Алгоритм быстрой сортировки
Сложность алгоритма быстрой сортировки
Сложность алгоритма быстрой сортировки
Достоинства: Самый быстродействующий из всех существующих
Достоинства: Самый быстродействующий из всех существующих
Спасибо за внимание
Спасибо за внимание

Презентация на тему: «Сложность, сортировка, поиск». Автор: 123. Файл: «Сложность, сортировка, поиск.ppt». Размер zip-архива: 325 КБ.

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

содержание презентации «Сложность, сортировка, поиск.ppt»
СлайдТекст
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

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

8

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

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

9

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

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

Виды поиска

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

Линейный поиск (последовательный поиск, поиск за линейное время) Двоичный (бинарный) поиск

10

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

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

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

11

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

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

Сложность

Сложность линейного поиска O(n)

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

12

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

Пример реализации алгоритма линейного поиска на языке 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 Описание метода бинарного поиска

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

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

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

16

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

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

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

В левой части повторяем алгоритм до тех пор, пока элемент-граница не равен 9

17

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

Пример реализации алгоритма бинарного поиска на языке 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++

Пример реализации алгоритма сортировки выборкой на языке 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

«Сложность, сортировка, поиск»
http://900igr.net/prezentacija/informatika/slozhnost-sortirovka-poisk-158513.html
cсылка на страницу
Урок

Информатика

130 тем
Слайды
900igr.net > Презентации по информатике > Поисковые системы > Сложность, сортировка, поиск