Алгоритмическое сокращение (Медиана медиан, быстрая сортировка)

Question

Я пытаюсь лучше понять сокращение, и в настоящее время я смотрю на два алгоритма: "Медиана медиан" и "Быстрая сортировка".

Я понимаю, что оба алгоритма используют аналогичную (эффективно идентичную) подпрограмму разбиения, чтобы помочь решить их проблемы, что в итоге делает их весьма похожими.

Select(A[1...n],k):  // Pseudocode for median of medians
  m = [n/5]
  for i from 1 to m:
    B[i] = Select(A[5i-4..5i],3)
  mom = Select(B[1..m],m/2)

  r = partition(A[1..n],mom)  // THIS IS THE SUBROUTINE

  if k < r:
    return Select(A[1..r-1],k)
  else if k > r:
    return Select(A[r+1..n],k-r)
  else
    return mom

Так имеет ли смысл термин "редукция" в отношении этих двух алгоритмов? Есть ли смысл в следующем?

• Медиана медиан / быстрой сортировки может быть уменьшена до подпрограммы раздела

• Медиана медиан сводится к быстрой сортировке

• Быстрая сортировка сводится к медиане медиан

Answer 1

Это действительно зависит от вашего определения "сокращения".

Стандартный тип сокращения, который обычно обсуждается, - это сокращение отображения (также называемое сокращением "многие-один"). Ниже приведена схема преобразования проблемы X в проблему Y:

Имея вход I _X для задачи X, преобразуйте его во вход I I для задачи Y. Затем запустите решатель для задачи Y на I _Y и выведите этот ответ.

При сокращении отображений вы получаете ровно один вызов подпрограммы, которая решает проблему Y, и вы должны вывести любой ответ, который вы получите от этой подпрограммы. Например, вы можете уменьшить проблему "это число даже?" на проблему "это число странно?" добавляя единицу к числу и выводя, является ли полученное число нечетным.

В качестве примера сокращения отображений рассмотрим следующие две проблемы: во-первых, проблема "является ли каждый логический элемент в этом списке истинным?", А во-вторых, проблема "является ли некоторый логический объект в этом списке ложным?" Если у вас есть решатель для второй задачи, вы можете использовать его для решения первой, запустив решатель для второй проблемы и вывив противоположный результат: список логических значений содержит некоторый элемент, который имеет значение false, если и только если это не тот случай, когда каждый элемент списка верен. Однако это сокращение не является отображением, потому что мы переворачиваем результат, полученный подпрограммой.

Другой тип сокращения, который часто используется, - это сокращение Тьюринга. Редукция Тьюринга от проблемы X к проблеме Y заключается в следующем:

Создайте алгоритм, который решает проблему X, предполагая, что существует волшебный черный ящик, который всегда решает проблему Y.

Все сокращения отображений являются сокращениями Тьюринга, но не наоборот. Вышеуказанное сокращение от "все ли верно?" "что-то ложное" - это не сокращение отображений, а сокращение Тьюринга, потому что вы можете использовать подпрограмму для "что-то ложное?" чтобы узнать, содержит ли список какие-либо ложные значения, можно вывести противоположное.

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

Вы можете рассматривать как быструю сортировку, так и медиану медиан как алгоритмы, которые используют разбиение в качестве подпрограммы. В быстрой сортировке эта подпрограмма выполняет всю тяжелую работу, необходимую для сортировки всего, а в медиане медиан она выполняет один из важных шагов, чтобы уменьшить ввод. Поскольку оба алгоритма выполняют несколько вызовов подпрограммы, вы можете думать о них как о сокращениях в стиле Тьюринга. Быстрая сортировка - это сокращение от сортировки до разбиения, в то время как медиана медианы - это сокращение от выбора до разбиения.

Надеюсь это поможет!

Answer 2

Я не думаю, что одно из них может быть сведено к другому (во всяком случае, значимым образом). Вы можете использовать медиану медиан, чтобы выбрать опору для быстрой сортировки (но практически никто не делает). Quicksort все еще должен выполнить некоторые другие шаги, основанные на элементе сводки (в частности, разделение данных на основе сводки).

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