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

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

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

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

Так имеет ли смысл термин «редукция» в отношении этих двух алгоритмов? Имеет ли что-либо из следующего смысл?

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

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

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


algorithm reduction quicksort median-of-medians
person cjhin    schedule 15.12.2013    source источник

Ответы (2)


arrow_upward
3
arrow_downward

Это действительно зависит от вашего определения «редукции».

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

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

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

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

Часто используется другой тип редукции — Тьюринг-редукция. Сведение Тьюринга от проблемы X к проблеме Y выглядит следующим образом:

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

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

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

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

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

person templatetypedef    schedule 15.12.2013

arrow_upward
0
arrow_downward

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

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

person Jerry Coffin    schedule 15.12.2013
comment
Потрясающе спасибо! Тогда ни одно из них не может быть сведено друг к другу. Но можно ли обе свести к той подпрограмме разделения, которую они обе используют для выбора точки опоры? - person cjhin; 16.12.2013
comment
@cjhin: Я так не думаю, но это, по крайней мере, достаточно близко, чтобы быть уверенным, нужно более тщательно подумать. - person Jerry Coffin; 16.12.2013