Действительно ли сравнение занимает время O(1)? а если нет, то почему мы используем сравнительные сортировки?

Рассмотрим два k-битных числа (в двоичном представлении):

$$A = A_1 A_2 A_3 A_4 ... A_k $$

$$B = B_1 B_2 B_3 B_4 ... B_k $$

чтобы сравнить, мы сканируем слева направо в поисках появления 0 и проверяем противоположное число, если эта цифра также является 0 (для обоих чисел), замечая, что если когда-либо такой случай будет найден, то источник 0 меньше, чем источник 1. Но что, если числа:

111111111111
111111111110

ясно, что это потребует сканирования всего числа, и если нам ничего не говорят о числах заранее, а просто дают их, то:

Сравнение занимает $O(k)$ времени.

Поэтому, когда мы смотрим на код метода сортировки, такого как высокопроизводительная быстрая сортировка:

HPQuicksort(list): T(n)
  check if list is sorted: if so return list
  compute median: O(n) time (or technically: O(nk))

  Create empty list $L_1$, $L_2$, and $L_3$ O(1) time

  Scan through list  O(n)

  if element is less place into $L_1$ O(k)

  if element is more place into $L_2$ O(k)

  if element is equal place into $L_3$ O(k)

  return concatenation of HP sorted $L_1$, $L_3$, $L_2$  2 T(n/2)

Таким образом: T(n) = O(n) + O(nk) + 2*T(n/2) ---> T(n) = O(nklog(n))

Это означает, что быстрая сортировка медленнее, чем сортировка по основанию.

Почему же мы до сих пор его используем?


sorting time-complexity quicksort complexity-theory radix-sort
person frogeyedpeas    schedule 14.02.2014    source источник
comment
Я вижу, mathjax здесь не работает. Как вы рекомендуете форматировать?   -  person frogeyedpeas    schedule 14.02.2014
comment
Форматирование кода. Он не такой многофункциональный, как MathJax, поскольку он в основном просто моноширинный, но это то, что у нас есть.   -  person user2357112 supports Monica    schedule 14.02.2014
comment
Извини, что? Сравнение реализовано в кремнии. Это занимает один цикл или около того. Можете уточнить, о чем именно вы говорите? Если вы сортируете экземпляры структуры данных BigInt с битами произвольной длины, конечно, я думаю, что это очень редкая вещь для сортировки. Если вы сортируете целые числа (32/64 бита): 1) это O (1), несмотря ни на что, потому что k ограничено. 2) Это даже не O(n) до предела, потому что делается мгновенно.   -  person GVH    schedule 14.02.2014
comment
Сортировка двух целых чисел требует вызова сравнения их битов. Если целые числа не имеют фиксированного размера, это не операция с постоянным временем.   -  person frogeyedpeas    schedule 14.02.2014
comment
И даже тогда очевидно, что сортировка по основанию быстрее, чем быстрая сортировка, если целые числа имеют фиксированный размер.   -  person frogeyedpeas    schedule 14.02.2014
comment
Не совсем так очевидно - нужно учитывать постоянный фактор.   -  person user2357112 supports Monica    schedule 14.02.2014
comment
Этот фактор - размер целых чисел, я думаю?   -  person frogeyedpeas    schedule 14.02.2014
comment
Нет, это не так. Постоянный фактор включает в себя управление памятью, относительную эффективность различных инструкций O(1), эффекты кэширования и т. д.   -  person user2357112 supports Monica    schedule 14.02.2014
comment
Большой плюс сравнительных сортировок в том, что сравнение носит общий характер. Мы можем сортировать сравнением все типы данных, но поразрядная сортировка работает только с целыми числами или вещами, которые мы можем преобразовать в целые числа.   -  person user2357112 supports Monica    schedule 14.02.2014
comment
Это зависит от контекста вычислительной сложности.   -  person Gumbo    schedule 14.02.2014
comment
Ваш анализ времени выполнения выглядит правильно, я согласен, что это будет O(k *n * log(n)). Насколько это актуально? Я мог бы придумать тип данных, который требует O(n!) времени для сравнения. Я мог бы придумать другой специализированный алгоритм сортировки, который может сортировать их за время O(n). Но единственный раз, когда мой алгоритм был бы лучше, был бы при сортировке этой конкретной вещи. В 99,99999% случаев алгоритм O(n * log(n)) будет лучшим вариантом.   -  person GVH    schedule 14.02.2014

Ответы (1)


arrow_upward
2
arrow_downward

Кажется, здесь два независимых вопроса:

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

  2. Зачем нам использовать быструю сортировку больших целых чисел вместо сортировки по основанию?

Для (1), как правило, анализ времени выполнения алгоритмов сортировки измеряется с точки зрения количества выполненных сравнений, а не с точки зрения общего количества выполненных операций. Например, знаменитая нижняя граница сортировки дает нижнюю границу с точки зрения количества сравнений, а анализ быстрой сортировки, пирамидальной сортировки, сортировки выбором и т. д. работает путем подсчета сравнений. Это полезно по нескольким причинам. Во-первых, как правило, алгоритм сортировки будет реализован путем предоставления массива и некоторой функции сравнения, используемой для их сравнения (например, qsort в C или Arrays.sort в Java). С точки зрения алгоритма сортировки это черный ящик. Поэтому имеет смысл проанализировать алгоритм, постаравшись минимизировать количество обращений к черному ящику. Во-вторых, если мы проводим анализ алгоритмов сортировки путем подсчета сравнений, тогда легко определить общее время выполнения, умножив количество сравнений на стоимость сравнения. Например, вы правильно определили, что сортировка n k-битных целых чисел займет ожидаемое время O(kn log n) с использованием быстрой сортировки, поскольку вы можете просто умножить количество сравнений на стоимость сравнения.

Что касается вашего второго вопроса — зачем нам использовать быструю сортировку больших целых чисел вместо сортировки по основанию? - как правило, вы фактически использовали бы сортировку по основанию в этом контексте, а не быструю сортировку, по конкретной причине, которую вы указали. Быстрая сортировка — отличный алгоритм сортировки для сортировки объектов, которые можно сравнивать друг с другом, и который имеет превосходную производительность, но сортировка по основанию часто превосходит его на больших массивах больших строк или целых чисел.

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

person templatetypedef    schedule 22.05.2014