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

Question

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

$$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))

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

Почему мы все еще используем его?

Answer 1

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

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

2. Почему мы используем quicksort для больших целых чисел вместо сортировки radix?

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

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

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