4.4. Нижние оценки для числа сравнений при сортировке

  •  
      Пусть имеется n различных по весу камней и весы, которые позволяют за одно взвешивание определить, какой из двух выбранных нами камней тяжелее. (В программистских терминах: мы имеем доступ к функции тяжелее(i,j:1..n):boolean.) Надо упорядочить камни по весу, сделав как можно меньше взвешиваний (вызовов функции "тяжелее").

      Разумеется, число взвешиваний зависит не только от выбранного нами алгоритма, но и от того, как оказались расположены камни. Сложностью алгоритма назовем число взвешиваний при наихудшем расположении камней.

      4.4.1. Доказать, что сложность любого алгоритма сортировки n камней не меньше log (n!). (Логарифм берется по основанию 2, n! - произведение чисел 1..n.)

      Решение. Пусть имеется алгоритм сложности не более d. Для каждого из n! возможных расположений камней запротоколируем результаты взвешиваний (обращений к функции "тяжелее"); их можно записать в виде последовательности из не более чем d нулей и единиц. Для единообразия дополним последовательность нулями, чтобы ее длина стала равной d. Тем самым у нас имеется n! последовательностей из d нулей и единиц. Все эти последовательности разные - иначе наш алгоритм дал бы одинаковые ответы для разных порядков (и один из ответов был бы неправильным). Получаем, что 2 в степени d не меньше n! - что и требовалось доказать.

      Другой способ объяснить то же самое - рассмотреть дерево вариантов, возникающее в ходе выполнения алгоритма, и сослаться на то, что дерево высоты d не может иметь более (2 в степени d) листьев.

      Это рассуждение показывает, что любой алгоритм сортировки, использующий только сравнения элементов массива и их перестановки, требует не менее C*n*log n действий, так что наши алгоритмы близки к оптимальным. Однако алгоритм сортировки, использующий другие операции, может действовать быстрее. Вот один из примеров.

      4.4.2. Имеется массив целых чисел a[1]..a[n], причем все числа неотрицательны и не превосходят m. Отсортировать этот массив; число действий порядка m+n.

      Решение. Для каждого числа от 0 до m подсчитываем, сколько раз оно встречается в массиве. После этого исходный массив можно стереть и заполнить заново в порядке возрастания, используя сведения о кратности каждого числа.

      Отметим, что этот алгоритм не переставляет числа в массиве, как большинство других, а "записывает их туда заново".

      Есть также метод сортировки, в котором последовательно проводится ряд "частичных сортировок" по отдельным битам. Начнём с такой задачи:

      4.4.3. В массиве a[1]..a[n] целых чисел переставить элементы так, чтобы чётные числа шли перед нечётными (не меняя взаимный порядок в каждой из групп).

      Решение. Сначала спишем (во вспомогательный массив) все чётные, а потом - все нечётные.

      4.4.4. Имеется массив из n чисел от 0 до (2 в степени k) - 1, каждое из которых мы будем рассматривать как k-битовое слово из нулей и единиц. Используя проверки "i-ый бит равен 0" и "i-ый бит равен 1" вместо сравнений, отсортировать все числа за время порядка n*k.

      Решение. Отсортируем числа по последнему биту (см. предыдущую задачу), затем по предпоследнему и так далее. В результате они будут отсортированы. В самом деле, индукцией по i легко доказать, что после i шагов любые два числа, отличающиеся только в i последних битах, идут в правильном порядке. (Вариант: после i шагов i-битовые концы чисел идут в правильном порядке.)

      Аналогичный алгоритм может быть применен для m-ичной системы счисления вместо двоичной. При этом полезна такая вспомогательная задача:

      4.4.5. Даны n чисел и функция f, принимающая (на них) значения 1..m. Требуется переставить числа в таком порядке, чтобы значения функции f не убывали (сохраняя притом порядок внутри каждой из групп). Число действий порядка m+n.

      Указание. Завести m списков суммарной длины n (как это сделать, смотри в главе 6 о типах данных) и помещать в i-ый список числа, для которых значение функции f равно i. Вариант: посчитать для всех i, сколько имеется чисел x c f(x)=i, после чего легко определить, с какого места нужно начинать размещать числа с f(x)=i.

Другие записи

10.06.2016. 4.1. Квадратичные алгоритмы
  4.1.1. Пусть a[1], ..., a[n] - целые числа. Требуется построить массив b[1], ..., b[n], содержащий те же числа, для которого b[1] <= ... <= b[n]. Замечание. Среди чисел a[1]...a[n] могут быть…
10.06.2016. 4.5. Родственные сортировке задачи
  4.5.1. Какова минимально возможная сложность (число сравнений в наихудшем случае) алгоритма отыскания самого легкого из n камней? Решение. Очевидный алгоритм с инвариантом "найден самый легкий камень…