Это не моя домашняя работа в школе. Это моя собственная домашняя работа, и я являюсь самообучающимися алгоритмами.
В Руководство по разработке алгоритмов, есть такой акциз
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) для сортировки таких последовательностей.
Но в основном для всех этих акцизов, мой интуитивный всегда думал о подсчете сортировки, поскольку мы можем знать диапазон элементов, а диапазон достаточно короток по сравнению с длиной всего массива. Но после более глубокого размышления, я думаю, что акцизы ищут, это второй подход, верно?
Спасибо
Мы можем просто создать хэш-карту, хранящую каждый элемент в качестве ключа, и его частоту как значение.
Отсортируйте эту карту в log(n)*log(log(n)) время i.e(klogk) с помощью любого алгоритма сортировки.
Теперь сканирует хэш-карту и добавляет элементы к новому числу частот в массиве. Например:
total time = 2n+log(n)*log(log(n)) = O(n)
Сортировка сортировки - один из возможных способов:
first_part_of_number.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).
Обновление: после того, как я написал ответ ниже, @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)) может купить вас много. Математик сказал бы компьютерному ученому эти десятилетия назад, но компьютерный ученый не слушал, спешил или не понимал смысла. И все в порядке. Я не против. Есть много и много очков по другим предметам, которые я не понимаю, даже когда очки тщательно объясняются мне. Но это то, что я считаю, что я действительно понимаю. По сути, это математическая точка, а не компьютерная точка, и это точка, с которой я столкнулся с Лебедевым и математиками, а не с Кнутом и компьютерными учеными. Это все.
Я собираюсь предать мои ограниченные знания алгоритмической сложности здесь, но:
Не имеет смысла сканировать массив один раз и строить что-то вроде дерева с балансировкой? Поскольку мы знаем, что количество узлов в дереве будет расти только до (log log n), это относительно дешево (?), Чтобы каждый раз находить число. Если число повторений найдено (вероятно), счетчик в этом случае node увеличивается. Затем, чтобы построить отсортированный массив, прочитайте дерево в порядке.
Возможно, кто-то может прокомментировать сложность этого и любые недостатки.