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

Автор: 123. Чтобы познакомиться с картинкой полного размера, нажмите на её эскиз. Чтобы можно было использовать все картинки для урока информатики, скачайте бесплатно презентацию «Сложность, сортировка, поиск.ppt» со всеми картинками в zip-архиве размером 325 КБ.

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

содержание презентации «Сложность, сортировка, поиск.ppt»
Сл Текст Сл Текст
1Сложность, сортировка, поиск. Работа 19дискретен, и изначально лежит на отрезке
по дисциплине «Алгоритмы и структуры длины n, поиск решения займёт (1+ log n)
данных» Выполнена Садукевич А.В., 271ПИ. времени. Сложность бинарного поиска O( log
1. n). 19.
2Введение. Теория сложности вычислений 20За: Относительная быстрота выполнения
возникла из потребности сравнивать поиска (по линейным). Против: Бинарный
быстродействие алгоритмов (например, поиск может применяться только на
алгоритмов поиска и сортировки), чётко упорядоченном множестве. 20.
описывать их поведение (время исполнения и 21Алгоритм сортировки. - алгоритм для
объём необходимой памяти) в зависимости от упорядочения элементов в списке. В случае,
размера входа. когда элемент списка имеет несколько
3Сложность. Время выполнения алгоритма полей, поле, служащее критерием порядка,
определяется количеством тривиальных называется ключом сортировки. Остальные
шагов, необходимых для решения проблемы и поля могут в ней не участвовать. 21.
зависит от размера входных данных (далее 22Характеристики алгоритмов сортировки.
n). Пространство объёмом памяти или места Устойчивость – изменение относительного
на носителе данных, используемом положения равных элементов Естественность
алгоритмом. Мера использования алгоритмом поведения – улучшение работы алгоритма при
ресурсов времени или пространства. 3. улучшении (частичной или полной
4Сложность. Асимптотическая оценка. F сортировке) входных данных Сравнения -
(n) – функция трудоемкости, определяющая количество операций сравнения элементов
зависимость между входными данными и Перестановки - количество перестановок
кол-вом базовых операций ( временными элементов. 22.
затратами алгоритма ). O(g(n)) = { f(n): 23Алгоритм сортировки подсчётом.
существуют положительные константы c и n0 алгоритм сортировки массива целых
такие, что 0? f(n) ? cg(n) для всех n? положительных чисел, лежащих в
n0}. 4. определённом диапазоне. При выполнении
5Классы оценок сложности. Множества этого алгоритма подсчитывается число
вычислительных проблем, для решения элементов, меньших текущего элемента х, и
которых известны алгоритмы, схожие по число одинаковых элементов, а затем
сложности. O(1) – постоянное время выстраивается новый массив, в который
o(log(n)) – логарифмическое время o(n) – элемент х записывается сразу «на свое
линейное время o(n log(n)) – место» (исходя из этих подсчётов). 23.
"n-log-n" время o(n2) – 24Схема реализации сортировки подсчётом.
квадратичное время o(n3) – кубическое // A[1..N] – входной массив, b[1..N] –
время o(2n) – экспоненциальное время. 5. выходной, c[1..K] - // вспомогательный, k-
6Примеры. Класс P. Проблемы, решение максимальное число элементов в массиве 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]
входных данных (например, O(n), O(n2)). равно количеству элементов, равных i for i
Сортировка Поиск во множестве Выяснение := 2 to k do c[i] := c[i] + c[i -1] c[i]
связности графов. 6. равно количеству элементов, не
7Примеры. Класс NP. Проблемы, для превосходящих i for j := length[a] downto
решения которых используются лишь 1 do b[c[a[j]]] := a[j] c[a[j]] :=
алгоритмы, экспоненциально зависящие от c[a[j]]-1. 24.
размера входных данных (например, O(2n)). 25Сложность. Циклы в строках 1-2 и 6-7
Задача коммивояжера Задача выполнимости работают за время O(k), Циклы в строках
булевых формул факторизация. 7. 3-4 и 10-11 - за время O(n), Значит, весь
8Время выполнения алгоритма для алгоритм работает за время O(n+k); если k=
небольших n. 8. O(n), то время работы (временная
9Время выполнения алгоритма для больших сложность) есть O(n). 25.
n. 9. 26За: Устойчивая сортировка: если во
10Алгоритм поиска. Виды поиска. - входном массиве присутствуют несколько
Алгоритм нахождения заданного значения одинаковых чисел, то в выходном массиве
произвольной функции в некотором наборе они стоят в том же порядке, что и во
значений. Линейный поиск (последовательный входном. Против: Ограничения, налагаемые
поиск, поиск за линейное время) Двоичный на входные данные (массив целых
(бинарный) поиск. 10. положительных чисел в известном
11Линейный (последовательный) поиск. - диапазоне). 26.
Простейший вид поиска заданного элемента 27Алгоритм сортировки выборкой. -
на некотором отрезке (множестве), неустойчивый алгоритм сортировки, при
осуществляемый путем последовательного котором выбирается минимальное значение,
сравнения очередного рассматриваемого производится обмен этого значения со
значения с искомым до тех пор, пока эти значением на первой позиции в списке
значения не совпадут. 11. (массиве, множестве). Эти операции
12Время выполнения. Сложность. Сложность повторяются с хвостом списка: исключаются
линейного поиска O(n). Если отрезок имеет уже отсортированные элементы – до тех пор,
длину n, то найти решение с точностью до ? пока весь список не будет отсортирован.
можно за время n/ ? 12. 27.
13Пример реализации алгоритма линейного 28Иллюстрация выполнения алгоритма
поиска на языке C++. Template <class сортировки выборкой. 1.Начальный массив
T> int linear_search(const 2.Минимальный элемент = 12 3. Минимальный
vector<t>& v, const T& item) элемент = 7 4…. Минимальный элемент = 3
{ for (int i = 0; i < v.Size(); i++) { Затем повторяются те же шаги без учёта
if (v[i] == item) { return i; // элемент отсортированного элемента 5. Итог –
найден } } return -1; // элемент не найден отсортированный массив. 28.
}. 13. 29Пример реализации алгоритма сортировки
14За: Не требует сортировки значений выборкой на языке 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Сложность алгоритма сортировки
элементов. 14. выборкой. На массиве из n элементов имеет
15Двоичный (бинарный) поиск. - поиск время выполнения в худшем, среднем и
заданного элемента на упорядоченном лучшем случае O(n2), предполагая что
множестве, осуществляемый путем сравнения делаются за постоянное время.
неоднократного деления этого множества на 30.
две части таким образом, что искомый 31Алгоритм быстрой сортировки. Алгоритм
элемент попадает в одну из этих частей. сортировки списка (множества, массива),
Поиск заканчивается при совпадении основанный на принципе «разделяй и
искомого элемента с элементом- границей властвуй», самый быстрый из известных
между частями множества или при отсутствии универсальных алгоритмов сортировки.
искомого элемента. 15. 32Алгоритм быстрой сортировки. Выбираем
16Описание метода бинарного поиска. в массиве некоторый элемент, который будем
Упорядоченное по возрастанию множество называть опорным элементом; Разделяем
элементов, необходимо найти элемент с массив таким образом, чтобы все элементы,
значением, равным 9. Выбор середины меньшие или равные опорному элементу,
вектора – элемента-границы. 16. оказались слева от него, а все элементы,
17Описание метода бинарного поиска. большие опорного — справа от него;
Сравнение элемента-границы с искомым Рекурсивно упорядочиваем подмассивы,
элементом: 9 < 21, отбрасываем правую лежащие слева и справа от опорного
часть. В левой части повторяем алгоритм до элемента; Базой рекурсии являются наборы,
тех пор, пока элемент-граница не равен 9. состоящие из одного или двух элементов.
17. Первый возвращается в исходном виде, во
18Пример реализации алгоритма бинарного втором, при необходимости, сортировка
поиска на языке C++. Template <class сводится к перестановке двух элементов.
T> int binary_search(const 33Сложность алгоритма быстрой
vector<t>& v, const T& item) сортировки. Лучший случай: O (n log n);
{ int low = 0; int high = v.Size() - 1; Промежуточный случай: O (n log n); Худший
int mid; while (low <= high) { // случай: O (n2);
нахождение элемента-границы mid = (low + 34Достоинства: Самый быстродействующий
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/?. Когда аргумент 35Спасибо за внимание! Москва, 2008. 35.
Сложность, сортировка, поиск.ppt
http://900igr.net/kartinka/informatika/slozhnost-sortirovka-poisk-158513.html
cсылка на страницу

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

другие презентации на тему «Сложность, сортировка, поиск»

«Поиск в интернете» - Ключевые слова из поля источника и поля методологии. Советы: удобны персоналии и термины. Учитывать ли (как и при рассылках) рекламу, замусоривание ящика… Знать, что хочешь найти. «Модель знаний». Аннотируйте, обязательно давайте названия. Содержание поискового запроса. «Концентрический» принцип. Обязательность слов, которых нет в источнике – опознание своей научной традиции.

«Поиск Google» - Рассмотрим окно подробнее… Поиск синонимов. Поиск точной фразы. Страница результатов поиска Google (нижняя часть). Написание слов через пробел – самый распространенный вариант запроса. Почему именно Google? По ссылкам можно перейти на конкретную страницу с результатами поиска. Ограничение по дате. Google предлагает службы, отсутствующие у других ПС (например, поиск в группах новостей).

«Поиск талантов» - Основной инструмент поиска талантов. Условия привлечения талантов как системы. Professionali.ru – сервис профессионального общения менеджеров и предпринимателей. Можно автоматически получать оповещения о сетевой активности людей. Наличие позитивного имиджа компании на рынке (HR-бренд). Пожалуй, достаточно.

«Поисковые системы» - Назначение знака "~". Поисковые системы. Сайты компаний. Классификация поисковых средств. Представление о способах и методах поиска информации в интернете. Язык запросов. Русскоязычный интернет. Представление о структуре интернета. Сетевые СМИ. Информационные компании. Тематические подборки ссылок.

«Поиск данных» - Бинарный поиск с использованием фиктивного «барьерного» элемента. Шаг 2. Рассмотрим лишь первые 4 элемента массива. Поиск информации. Задача. Идея бинарного метода. Значение элемента х вводится с клавиатуры. Большинство задач поиска сводится к поиску в таблице элемента с заданным значением. Иначе двоичный поиск или метод половинного деления.

Поисковые системы

24 презентации о поисковых системах
Урок

Информатика

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