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

Question

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

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

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

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

---

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

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

Затем примените счетную сортировку.Однако при настройке счетного массива (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 << n. </p>

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

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

Спасибо

Answer 1

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

Сортировать эту карту за log(n)*log(log(n)) время, т. Е. (Klogk), используя любой алгоритм сортировки.

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

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

Answer 2

Обновление: После того, как я написал ответ ниже, @Nabb показал мне, почему он был неверным. Для получения дополнительной информации см. краткую запись Википедии на Õ и ссылки на нее. Хотя бы потому, что все еще необходимо предоставить контекст для комментариев @ Nabb's и @ 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 ^ (м-эпсилон)) расходится для z большой величины и действительного, положительного эпсилона сколь угодно малого величина. z может быть реальным или сложным, хотя, как мы говорили, epsilon должно быть реальным. При таком понимании примените правило Л'Оспиталя к функции O (n * log (n)), чтобы убедиться, что оно не отличается по порядку от функции O (n).

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

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

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

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

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

Answer 3

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

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

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

Answer 4

Подсчет сортировки является одним из возможных способов:

1. Я продемонстрирую это решение на примере 2, 8, 1, 5, 7, 1, 6, и все числа
2. Сначала для каждого числа A [i] вычисляем A [i] / N. Позволяет назвать этот номер first_part_of_number.
3. Сортировать этот массив, используя сортировку с подсчетом по first_part_of_number.

4. Результаты в форме (пример для N = 3)

   (0, 2)
   (0, 1)
   (0, 1)
   (2, 8)
   (2, 6)
   (2, 7)
   (2, 6)

5. Разделите их на группы по first_part_of_number.

6. В этом примере у вас будут группы
   (0, 2) (0, 1) (0, 1)

   и

   (2, 8) (2, 6) (2, 7) (2, 6)

7. Для каждого числа вычисляем 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)

8. Сортировка каждой группы с помощью подсчета сортировки по 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)

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

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