Алгоритм - Сортировка массива с различными элементами LogLogN

Это не моя домашняя работа в школе. Это моя собственная домашняя работа, и я являюсь самообучающимися алгоритмами.

В Руководство по разработке алгоритмов, есть такой акциз

4-25 Предположим, что массив A [1..n] имеет только цифры из {1,.,, n ^ 2}, но не более, чем log log n этих чисел. Разработать алгоритм, который сортирует A по существу меньше O (n log n).

У меня есть два подхода:

Первый подход:

В основном я хочу сделать подсчет сортировки для этой проблемы. Я могу сначала просмотреть весь массив (O (N)) и поместить все различные числа в массив размера loglogN (int [] K).

Затем примените сортировку counting. Однако при настройке счетного массива (int [] C) мне не нужно устанавливать его размер как N ^ 2, вместо этого я также устанавливаю размер как loglogN.

Но таким образом, при подсчете частот каждого отдельного числа, я должен сканировать массив K, чтобы получить этот индекс элемента (O (NloglogN), а затем обновить массив C.

Второй подход:

Опять же, мне нужно отсканировать весь массив, чтобы получить отдельный массив чисел K с размером loglogN.

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

Я думаю, что этот подход будет лучшим, с O (NlogloglogN).

Я прав? или есть лучшие решения?

Подобные акцизы существуют в Руководстве по проектированию алгоритмов, например

4-22 Покажите, что n положительных целых чисел в диапазоне от 1 до k можно сортировать по времени O (n log k). Интересным случаем вл етс, когда k < п.

4-23 Мы стремимся сортировать последовательность S из n целых чисел со многими дублированиями, так что число различных целых чисел в S равно O (log n). Дайте алгоритм наихудшего временного времени O (n log log n) для сортировки таких последовательностей.

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

Спасибо

Ответ 1

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

Отсортируйте эту карту в log(n)*log(log(n)) время i.e(klogk) с помощью любого алгоритма сортировки.

Теперь сканирует хэш-карту и добавляет элементы к новому числу частот в массиве. Например:

total time = 2n+log(n)*log(log(n)) = O(n)

Ответ 2

Сортировка сортировки - один из возможных способов:

Я продемонстрирую это решение на примерах 2, 8, 1, 5, 7, 1, 6, и все числа равны <= 3 ^ 2 = 9. Я использую больше элементов, чтобы сделать мою идею более понятной.
Сначала для каждого числа A [i] вычислить A [i]/N. Позволяет называть это число first_part_of_number.
Сортировка этого массива с помощью сортировки count first_part_of_number.
Результаты приведены в форме (пример для N = 3)

(0, 2)
(0, 1)
(0, 1)
(2, 8)
(2, 6)
(2, 7)
(2, 6)
Разделите их на группы на first_part_of_number.
В этом примере у вас будут группы (0, 2) (0, 1) (0, 1)

и

(2, 8) (2, 6) (2, 7) (2, 6)
Для каждого числа вычислить X по модулю N. Позволяет называть его second_part_of_number. Добавьте этот номер в каждый элемент
(0, 2, 2) (0, 1, 1) (0, 1, 1)

и

(2, 8, 2) (2, 6, 0) (2, 7, 1) (2, 6, 0)
Сортировка каждой группы с помощью сортировки подсчета second_part_of_number

(0, 1, 1) (0, 1, 1) (0, 2, 2)

и

(2, 6, 0) (2, 6, 0) (2, 7, 1) (2, 8, 2)
Теперь объедините все группы, и у вас есть результат 1, 1, 2, 6, 6, 7, 8.

Сложность: Вы использовали только подсчет сортировки по элементам <= N. Каждый элемент принимал участие ровно в 2 "сортах". Таким образом, общая сложность O (N).

Ответ 3

Обновление: после того, как я написал ответ ниже, @Nabb показал мне, почему это было неправильно. Для получения дополнительной информации см. Краткое описание Википедии на Õ и ссылки из нее. По крайней мере потому, что по-прежнему необходимо придавать контекст комментариям @Nabb и @Blueshift, и поскольку все обсуждение остается интересным, мой первоначальный ответ сохраняется следующим образом.

ОРИГИНАЛЬНЫЙ ОТВЕТ (НЕПРАВИЛЬНЫЙ)

Позвольте мне предложить нетрадиционный ответ: хотя действительно существует разница между O (n * n) и O (n), нет разницы между O (n) и O (n * log (n)).

Теперь, конечно, мы все знаем, что то, что я только что сказал, ошибочно, не так ли? В конце концов, различные авторы согласны с тем, что O (n) и O (n * log (n)) отличаются.

За исключением того, что они не отличаются.

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

Математически, по существу, порядок m функции f (z) таков, что f (z)/(z ^ (m + epsilon)) сходится, а f (z)/(z ^ (m-epsilon)) расходится для z большой величины и реального положительного эпсилона сколь угодно малой величины. Z может быть реальным или сложным, хотя, как мы сказали, epsilon должен быть реальным. При таком понимании примените правило L'Hospital к функции O (n * log (n)), чтобы увидеть, что он не отличается по порядку от функции O (n).

Я бы утвердил, что принятая в настоящее время компьютерно-научная литература немного ошибочна в этом вопросе. Эта литература в конечном итоге усовершенствует свою позицию в этом вопросе, но пока этого не сделала.

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

Кстати, противоположная импликация этой позиции ответа заключается в том, что можно получить доступ к сбалансированному двоичному дереву в O (1) раз. Опять же, мы все знаем, что это ложь, не так ли? Он должен быть O (log (n)). Но помните: нотация O() никогда не предназначалась для точной оценки вычислительных требований. Если n не очень велико, другие факторы могут быть более важными, чем порядок функций. Но даже при n = 1 миллион log (n) составляет всего 20, сравнивается, скажем, с sqrt (n), что равно 1000. И я мог бы продолжать в этом ключе.

В любом случае, подумайте. Даже если, в конце концов, вы решите, что не согласны со мной, вы можете найти позицию, интересную тем не менее. Со своей стороны, я не уверен, насколько полезной является O() нотация, когда дело доходит до O (log something).

@Blueshift задает некоторые интересные вопросы и поднимает некоторые правильные моменты в комментариях ниже. Я рекомендую вам прочитать его слова. Мне действительно нечего добавить к тому, что он должен сказать, за исключением того, что это видно из-за того, что немногие программисты (или нуждаются) в обосновании математической теории сложной переменной, O (log (n)) нотация, скорее всего, ввела в заблуждение, буквально сотни тысяч программистов, полагая, что они достигают в основном иллюзорных достижений в вычислительной эффективности. Редко на практике уменьшает O (n * log (n)) до O (n), действительно покупает вам то, что вы можете подумать, что оно покупает вас, если у вас нет четкого мысленного образа того, насколько невероятно медленной функция логарифма - тогда как уменьшение O (n) даже до O (sqrt (n)) может купить вас много. Математик сказал бы компьютерному ученому эти десятилетия назад, но компьютерный ученый не слушал, спешил или не понимал смысла. И все в порядке. Я не против. Есть много и много очков по другим предметам, которые я не понимаю, даже когда очки тщательно объясняются мне. Но это то, что я считаю, что я действительно понимаю. По сути, это математическая точка, а не компьютерная точка, и это точка, с которой я столкнулся с Лебедевым и математиками, а не с Кнутом и компьютерными учеными. Это все.

Ответ 4

Я собираюсь предать мои ограниченные знания алгоритмической сложности здесь, но:

Не имеет смысла сканировать массив один раз и строить что-то вроде дерева с балансировкой? Поскольку мы знаем, что количество узлов в дереве будет расти только до (log log n), это относительно дешево (?), Чтобы каждый раз находить число. Если число повторений найдено (вероятно), счетчик в этом случае node увеличивается. Затем, чтобы построить отсортированный массив, прочитайте дерево в порядке.

Возможно, кто-то может прокомментировать сложность этого и любые недостатки.