Сортировка слиянием и сортировка по основанию: сортировка слиянием занимает время O (n (log n) ^ 2) в особых случаях?

Я читал об эффективности сортировки Radix по сравнению с алгоритмами сортировки на основе сравнения, где я нашел это кусок :

Например, рассмотрим сортировку слиянием снизу вверх. При первом проходе будут сравниваться пары случайных ключей, а при последнем проходе будут сравниваться ключи, очень близкие в порядке сортировки. Это приводит к тому, что сортировка слиянием для этого класса входных данных занимает время O (n (log n) 2).

Может ли кто-нибудь помочь мне понять часть O(n (log n)2)?


time sorting algorithm mergesort radix-sort
person Somjit    schedule 13.03.2016    source источник
comment
По сути, он утверждает, что для сортировки набора данных с уникальными ключами наивно моделировать операции сравнения O(1) по мере того, как набор растет до бесконечности. Для плотного набора вам потребуются ключи по крайней мере log n сложности, и поэтому алгоритм сортировки может в конечном итоге потратить много времени на сравнение общих префиксов почти одинаковых ключей к концу прогона. Алгоритм сортировки может повысить производительность за счет более глубокой проверки структуры ключей, например, при сортировке по основанию или быстрой сортировке с отслеживанием и пропуском общих строковых префиксов.   -  person doynax    schedule 13.03.2016

Ответы (1)


arrow_upward
1
arrow_downward

Предполагая постоянное время сравнения == O (1), тогда сортировка слиянием равна O (n log (n)). Если предположить, что время сравнения равно O (log (n)), то сортировка слиянием будет O (N (log (n)) ^ 2). Предположение здесь основано на минимальном размере ключа для n различных ключей, что составляет log2(n) бит. Однако размер ключа обычно не зависит от n и либо является постоянным, либо постоянным является средний размер всех ключей в наборе из n элементов, и в этом случае временная сложность составляет O (n log (n)).

Речь идет скорее о сортировке по основанию, где количество проходов зависит от того, на сколько частей разделен ключ. Например, если ключ имеет длину 64 бита, а поразрядная сортировка выполняется по 4 бита за раз, потребуется 16 проходов. Если размер ключа составляет 28 символов, а сортировка по основанию выполняется по одному символу за раз, то потребуется 28 проходов. Если рассматривать минимальный размер ключа для n различных ключей, который составляет log2(n) бит, и если сортировать по 8 бит за раз, то требуется log256(n) проходов. Например, сортировка 2^32 ключей означает, что ключи имеют размер 32 бита, а сортировка по 8 битам за один раз займет 4 прохода. Для ключей 2^64 это 64 бита на ключ и 8 проходов.

person rcgldr    schedule 13.03.2016