Презентация Сортировки. Двоичный поиск онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Сортировки. Двоичный поиск абсолютно бесплатно. Урок-презентация на эту тему содержит всего 25 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:25 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:693.20 kB
- Просмотров:57
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№1 слайд
Содержание слайда: Сортировки.
Двоичный поиск.
№2 слайд
Содержание слайда: Быстрая сортировка (Ч. Хоар, 1962)
Идея: «разделяй и властвуй»
Среднее время работы – O(n log n)
В худшем случае – O()
В обычной реализации неустойчива
№3 слайд
Содержание слайда:
№4 слайд
Содержание слайда: Сортировка слиянием (Дж. Фон Нейман, 1945)
Идеи: «разделяй и властвуй», слияние отсортированных массивов
Время работы – О()
Сортировка устойчива
№5 слайд
Содержание слайда:
№6 слайд
Содержание слайда: Пирамидальная сортировка
Идея: использование кучи
Время работы – О()
Сортировка неустойчива
Сортировка разбиралась на теме:
«Структуры данных»
№7 слайд
Содержание слайда: Сортировка подсчётом
Идея: использование конечной длины сортируемых чисел
Время работы – O(n)
Сортировка устойчива
№8 слайд
Содержание слайда:
№9 слайд
Содержание слайда: Двоичный поиск
Двоичный поиск — алгоритм поиска объекта по заданному признаку в множестве объектов, упорядоченных по тому же самому признаку, работающий за логарифмическое время.
№10 слайд
Содержание слайда: Задача
Пусть нам дан упорядоченный массив, состоящий только из целочисленных элементов. Требуется найти позицию, на которой находится заданный элемент или сказать, что такого элемента нет.
№11 слайд
Содержание слайда: Принцип работы
Двоичный поиск заключается в том, что на каждом шаге множество объектов делится на две части и в работе остаётся та часть множества, где находится искомый объект.
№12 слайд
Содержание слайда:
№13 слайд
Содержание слайда: Задача
Пусть у нас есть N принтеров и нам нужно напечатать К листовок. Каждый принтер печатает одну листовку за секунд. Сколько нам потребуется минимальное количество времени, чтобы напечатать все листовки?
= ,
№14 слайд
Содержание слайда: Задачу можно решить с помощью двоичного поиска по ответу.
Задачу можно решить с помощью двоичного поиска по ответу.
Будем искать двоичным методом время, за которое мы сможем напечатать все листовки.
Для каждого время мы сможем за O(N) проверить этот факт.
Так как функция Количество_листовок(время) монотонна, следовательно здесь применим двоичный поиск
Получим решение за O(n log ())
№15 слайд
Содержание слайда: Как сам двоичный поиск, так и метод двоичного поиска по ответу очень(!) часто встречается в задачах.
Как сам двоичный поиск, так и метод двоичного поиска по ответу очень(!) часто встречается в задачах.
Рассмотрим ещё одну задачу:
Пусть нам задана монотонная функция и два значения аргумента x1, x2. Сказано, что на отрезке [x1;x2] имеется ровно один корень функции, т.е. и f(x1)*f(x2) < 0.
Нужно найти х.
№16 слайд
Содержание слайда: Некоторые полезные советы при работе с вещественными числами
№17 слайд
Содержание слайда: Когда имеешь дело с вещественными числами в первую очередь нужно подумать нельзя ли от них избавиться и перейти к целым.
Когда имеешь дело с вещественными числами в первую очередь нужно подумать нельзя ли от них избавиться и перейти к целым.
Пример 1:
Нам нужно сравнить два числа вида a/b, где а и b целые числа
№18 слайд
Содержание слайда: Неправильный выбор:
Неправильный выбор:
If ((double)a/b < (double)с/d)
Правильный выбор:
If (a * d < c * b)
Исключение:
Когда a * d или c * b не помещаются в целочисленный тип
№19 слайд
Содержание слайда: Пример 2:
Пример 2:
Нам нужен цикл до sqrt(n) включительно.
Неправильный выбор:
for(int i = 0; i <= sqrt(n); i++)
Правильный выбор:
for(int i = 0; i * i <= n; i++)
№20 слайд
Содержание слайда: Пример 3:
Пример 3:
Сравнить расстояния между точками a,b и c,d
int d1 = sqr(a.x-b.x) + sqr(a.y-b.y);
int d2 = sqr(c.x-d.x) + sqr(c.y-d.y);
Вместо:
if (sqrt(d1) < sqrt(d2))
Лучше:
if (d1 < d2)
№21 слайд
Содержание слайда: Если всё-таки приходится работать с вещественными числами, то всегда нужно стараться уменьшить погрешность вычислений
Если всё-таки приходится работать с вещественными числами, то всегда нужно стараться уменьшить погрешность вычислений
Пример 1:
b/a + c/a + … = (b + c + …)/a;
№22 слайд
Содержание слайда: Пример 2:
Пример 2:
У нас есть прямоугольный треугольник, мы знаем длины его сторон a,b,c и один из углов A. Нужно найти sin(B)
Не лучший выбор:
sinb = sin(pi - A);
Можно так:
sinb = b/c;
№23 слайд
Содержание слайда: Если у нас возможно равенство вещественных чисел, то их всегда нужно сравнивать по eps
Если у нас возможно равенство вещественных чисел, то их всегда нужно сравнивать по eps
abs(a - b) < eps <=> a == b
Eps должен быть меньше требуемой точности, но больше лучшей точности.
Обычно выбирают eps = 1e-9;
А вообще вопрос точности при работе с вещественными типами это философский вопрос
№24 слайд
Содержание слайда: При работе с бинпоиском, если нам нужно найти число с какой-то точностью, то почти всегда лучше это делать итерационно
При работе с бинпоиском, если нам нужно найти число с какой-то точностью, то почти всегда лучше это делать итерационно
Пример:
Нам нужно найти корень функции с заданной точностью
Не правильный выбор:
while((r – l) < eps)
Правильный выбор:
for (int i = 0; i < 100; i++)
№25 слайд
Содержание слайда: Полезные ссылки
goo.gl/KKdq1i – представление вещественных чисел в памяти компьютера
Скачать все slide презентации Сортировки. Двоичный поиск одним архивом:
