Я надеюсь, что кто-то знает ссылку на это, поэтому мне не нужно читать литературу ... Рассмотрим последовательность чисел . Думайте о последовательности как о n - 1 интервалах [ x 1 , x 2 ] , [ x 2 , x 3 ] , … , [ x n - 1 , x n ] . Ясно, что исходная последовательность является битовой, если любая...
В недавнем препринте https://arxiv.org/abs/1801.00776 утверждается, что вещественных чисел можно отсортировать по времени и линейному пространству. Статья кажется разумной, хотя я не эксперт в алгоритмах сортировки.nnnO(nlogn−−−−√),O(nlogn),O(n \sqrt{\log n}), Если это правильно, это будет...
Это интересный вопрос, который я нашел в Интернете. Для данного массива, содержащего n чисел (без информации о них), мы должны предварительно обработать массив за линейное время, чтобы мы могли вернуть k наименьших элементов за время O (k), когда нам дано число 1 <= k <= n Я обсуждал эту...
Хорошо известно , что сортировка перестановок транспонирования в , так как минимальное число транспозиций требуется для сортировки л ∈ S п точно я п V ( л ) = { ( я , J ) ∈ [ п ] × [ N ] : i < j и π ( i ) > π ( j ) }PP\sf{P}π∈Snπ∈Sn\pi \in...
Итак, мы все знаем нижнюю границу дерева сравнения на количество худших случаев сравнений, выполненных (детерминистическим) алгоритмом сортировки сравнений. Это не относится к рандомизированной сортировке сравнения (если мы измеряем ожидаемые сравнения для наихудшего случая). Например, для n = 4...
Этот вопрос основан на существующем вопросе о том, можно ли моделировать стек с использованием двух очередей с амортизированным раз на операцию стека. Ответ кажется неизвестным. Вот более конкретный вопрос, соответствующий особому случаю, когда сначала выполняются все операции PUSH, а затем все...
Предположим, что нам дан массив содержащий неотрицательные целые числа (не обязательно различающиеся).A[1..n]A[1..n]A[1..n] Пусть будет отсортированным в неубывающем порядке. Мы хотим вычислить BBBAAAm=maxi∈[n]B[i]+i.m=maxi∈[n]B[i]+i.m = \max_{i\in [n]} B[i]+i. Очевидным решением является...
Зафиксируем конечную группу . Меня интересует следующая проблема решения: входными данными являются некоторые элементы группы с частичным порядком на них, и вопрос заключается в том, существует ли перестановка элементов, которая удовлетворяет порядку и такова, что композиция элементов в этом...
Пусть , быть ориентированный ациклический граф , и пусть - функция маркировки отображения каждой вершины с меткой в некотором конечном алфавите . Запись, А топологическая сортировка из является взаимно однозначное от к (т.е., упорядочение в последовательности) таким образом, что всякий раз , когда...
Существует ли алгоритм сортировки, основанный на сравнении, который использует среднее из сравнений ?l g (n!)+o(n)lg(n!)+o(n)\mathrm{lg}(n!)+o(n) Существование алгоритма сравнения в худшем случае является открытой проблемой, но среднего случая достаточно для рандомизированного алгоритма с...
Все мы знаем, что минимальная сложность алгоритма сортировки на основе сравнения Ω ( n logн )Ω(NжурналN)\Omega(n \log n)сравнения. Я пытаюсь сделать слепой сортировку, т.е. с учетом числаNNn вывести схему (с логическими, арифметическими и "сравнительными" вентилями), которая сортирует список NNn...
Прошу прощения за краткость названия, я, возможно, пожертвовал ясностью на алтаре краткости. Можно видеть, что вставка элементов массива в двоичное дерево поиска и их повторное чтение требует (при вставке) тех же сравнений, что и запуск Quicksort для этого массива. Последовательность точек, которую...
Я смущен. Я хочу доказать, что это проблема сортировкиnNn по nnn матрица, т.е. строки и столбцы в порядке возрастания Ω(n2logn)Ω(n2logn)\Omega(n^2\log n), Я исхожу из предположения, что это можно сделать быстрее, чемn2lognn2lognn^2\log n и попытаться нарушить log(m!)log(m!)\log(m!) нижняя...