Начало
Учебные материалы
Метод преобразования
Идея метода преобразования Предварительная сортировка Метод исключения Гаусса Пирамиды и пирамидальная сортировка Схема Горнера Приведение задачи
Предварительная сортировка
что ряд задач с участием списков решаются существенно проще, если списки
отсортированы. Понятно, что временная эффективность алгоритма, включающего
в качестве этапа сортировку, может зависеть от эффективности
использованного алгоритма сортировки.
--
**Проверка уникальности элементов массива**.
Алгоритм на основе грубой силы для проверки того, что все элементы массива различны, попарно сравнивает все
элементы этого массива, пока не будут найдены два одинаковых либо пока не
будут пересмотрены все возможные пары. В наихудшем случае эффективность
такого алгоритма равна `Theta(n^2)`.
К решению задачи можно подойти и по-другому —
сначала отсортировать массив, а затем сравнивать только последовательные элементы: если в массиве
есть одинаковые элементы, то они должны следовать в отсортированном массиве один за другим.
--
Алгоритм Uniqueness (`A`)
// Входные данные: Массив `A[0...n-1]`
// Выходные данные: true, если в `A` нет одинаковых элементов,
// и false, если есть
Сортировка массива `A`
**for** `i in [0...n-2]` **do**
`quad` **if** `A[i] =A[i + 1]`
`quad quad quad` **return** false
**return** true
--
Время работы данного алгоритма представляет собой сумму времени,
затраченного на сортировку, и времени на проверку соседних элементов. Поскольку
для сортировки требуется как минимум `n log n` сравнений, а для проверки
соседних элементов — не более `n-1`, именно сортировка и определяет общую
эффективность алгоритма:
`T(n) = T_{"sort"}(n) + T_{"scan"}(n) in Theta (n log n) + Theta (n) = Theta (n log n)`.
--
*Модой* называется значение, которое
встречается в данном списке чаще других. Например, в случае значений 5, 1,5,
7, 6, 5, 7 модой является значение 5 (если одинаково часто встречается несколько
значений, модой может быть выбрано любое из них). Алгоритм на основе грубой
силы сканирует весь список и вычисляет количество появлений в списке каждого
из значений, из которых выбирается наибольшее.
--
При каждой итерации `i`-ый элемент исходного списка сравнивается со всеми значениями в списке для подсчета количества.
В результате количество сравнений равно:
`C(n)=sum_{i=1}^n n=n^2 in Theta(n^2)`.
Рассмотрим альтернативный вариант, начинающийся с сортировки списка.
В таком случае все равные значения будут соседствовать друг с другом, и для
вычисления моды надо только найти наибольшую подпоследовательность
одинаковых соседних значений в отсортированном списке.
--
Алгоритм Mode (`A`)
// Входные данные: Массив `A[0...n-1]`
// Выходные данные: Мода массива
Сортировка массива `A`
`i larr 0` // Текущая позиция
`mcount larr 0` // Максимальное количество одинаковых элементов
**while** `i < n` **do**
`quad l en larr 1; val larr A[i]`
`quad` **while** `i+l en < n and A[i+l en] = val` **do**
`quad quad quad l en larr l en + 1`
`quad` **if** `l en > mcount`
`quad quad quad mcount larr l en; m ode larr val`
`quad i larr i+l en`
**return** `m ode`
--
Время работы алгоритма определяется временем сортировки, поскольку время выполнения
остальной части алгоритма —
линейное. Следовательно, при
использовании сортировки, принадлежащей классу эффективности `n log n`, эффективность
описанного алгоритма будет выше эффективности алгоритма с использованием грубой силы.
--
Рассмотрим поиск данного значения `K` в массиве из `n`
элементов. Решение с использованием грубой силы —
последовательный поиск — требует в наихудшем случае `n` сравнений. Если
массив предварительно отсортировать, то применение бинарного поиска приведет
к `|__ log_2 n __| + 1` сравнений в наихудшем случае. Даже при использовании
максимально эффективной сортировки класса `n log n` общее время работы алгоритма
в наихудшем случае составит
`T(n) = T_{"sort"} (n) + T_{"search"}(n) = Theta(n log n) + Theta(log n) = Theta(n log n)`,
что хуже, чем в случае последовательного поиска.
То же самое можно сказать и об эффективности в среднем случае.
Конечно, если поиск требуется выполнять
неоднократно, то затраты времени на сортировку могут оказаться оправданными.
---
##### Задания для практики
1. Медианой множества из `n` чисел называется его `|__ n//2 __|` в порядке возрастания элемент (т.е. медиана больше одной половины элементов множества и меньше другой). Разработайте алгоритм для поиска медианы с использованием предварительной сортировки и определите класс его эффективности.
2. Рассмотрим задачу поиска расстояния между двумя ближайшими числами в массиве из `n` чисел (расстояние между двумя числами `x` и `y` вычисляется как `|x-y|`).\
а) Разработайте алгоритм с использованием предварительной сортировки для решения данной задачи и определите его класс эффективности.\
б) Сравните эффективность разработанного вами алгоритма с эффективностью алгоритма грубой силы.
3. Пусть `A ={a_1, a_2,..., a_n}` и `B={b_1, b_2, ..., b_m}` -- два множества чисел. Рассмотрим задачу поиска их пересечения, т.е. множества `C` всех чисел, которые входят как в `A`, так и в `B`.\
а) Разработайте алгоритм грубой силы для решения данной задачи и определите класс его эффективности.\
б) Разработайте алгоритм с использованием предварительной сортировки для решения данной задачи и определите класс его эффективности.
4. Рассмотрим задачу поиска наибольшего и наименьшего элементов в массиве их `n` чисел.\
а) Разработайте алгоритм с использованием предварительной сортировки для решения данной задачи и определите класс его эффективности.\
б) Сравните эффективность трех алгоритмов: 1) алгоритма грубой силы, 2) алгоритма с использованием предварительной сортировки и 3) алгоритма декомпозиции.
5. Дано множество из `n>=3` точек на плоскости. Требуется соединить их замкнутой ломаной линией без самопересечений так, чтобы получился многоугольник. Всегда ли поставленная задача имеет решение? Всегда ли это решение единственно? Разработайте эффективный алгоритм для решения поставленной задачи и определите его класс эффективности.
6. У вас есть массив из `n` чисел и целое число `S`. Определите, имеются ли в массиве два числа, сумма которых равна `S`. Например, в случае массива `[5, 9, 1, 3]` и `S=6` ответ —"да", но если `S=7`, ответ — "нет". Разработайте алгоритм для решения поставленной задачи, эффективность которого превышает квадратичную.
7. Разработайте эффективный алгоритм для поиска всех множеств анаграмм в большом файле, как, например, словарь английских слов. Например, eat, ate и tea принадлежат к одному такому множеству.
