По заданной последовательности элементов найдите перестановку, в которой элементы расположены в определенном порядке.
Существуют ли известные алгоритмы сортировки сравнений, которые не сводятся к сеткам сортировки, чтобы каждый элемент сравнивался раз?O(logn)O(logn)O(\log n) Насколько я знаю, единственный способ сортировки по для каждого элемента состоит в том, чтобы построить сеть сортировки AKS для n входов и...
Кто-нибудь знаком с Йиджи Хана , линейным пространством, алгоритмом целочисленной сортировки? Этот результат появляется в довольно короткой статье ( Детерминированная сортировка по времени и линейного пространства . J. Alg. 50: 96–105, 2004), которая в основном склеивает множество более ранних...
Существует ли структура данных, которая принимает неупорядоченный массив из элементов, выполняет предварительную обработку в и отвечает на запросы: есть ли какой-то элемент в списке, каждый запрос в наихудшее время ?O ( n ) x O ( log n )nnnO(n)O(n)O(n)xИксxO(logn)О(журналN)O(\log n) Я...
Некоторое время я думал о следующей проблеме, и я не нашел ее полиномиального решения. Только грубая четверка. Я тоже пытался свести к этому проблему NP-Complete, но безуспешно. Вот проблема : У вас есть отсортированный набор пар целых положительных чисел....
Том III книги Кнута « Искусство компьютерного программирования» (глава 5, стих 3.2) включает в себя следующую таблицу, в которой перечислено точное минимальное количество сравнений, необходимых для выбора наименьшего элемента TTt из несортированного набора размера NNn для всех 1 ≤ t ≤ n ≤...
O(nlogn)O(nlogn)O(n\log n)1+O(n−c)1+O(n−c)1+O(n^{-c})cccO(n)O(n)O(n)(max−min)n−(c+1)(max−min)n−(c+1)(\max-\min)n^{-(c+1)}его первоначального значения, а затем используйте основную сортировку. Но модели с округлением имеют проблематичную теорию сложности, и это заставило меня задуматься, а как...
Предположим, что мы хотим отсортировать список из действительных чисел. Предположим, что нам дан черный ящик, который может мгновенно отсортировать реальных чисел. Какое преимущество мы можем получить, используя этот черный ящик?n √SSSNnnN--√n\sqrt n Например, можем ли мы отсортировать номера...
Справочная информация: Чао Сюй некоторое время назад опубликовал следующий вопрос: « Существуют ли какие-либо известные алгоритмы сортировки сравнения, которые не сводятся к сортировке сетей, так что каждый элемент сравнивается раз?O(logn)O(logn)O(\log n) ». Кажется, мы немного застряли в...
Можно ли алгоритмически проверить, является ли вычисляемое число рациональным или целым? Другими словами, возможно ли для библиотеки, которая реализует вычислимые числа, предоставлять функции isIntegerили isRational? Я предполагаю, что это невозможно, и что это как-то связано с тем, что невозможно...
- это множество точек на плоскости. Случайная точка x ∉ S задается на той же плоскости. Задача состоит в том, чтобы отсортировать все y ∈ S по евклидову расстоянию между x и y .SSSx∉Sx∉Sx \notin Sy∈Sy∈Sy \in Sxxxyyy Бездумный подход состоит в том, чтобы вычислить расстояния между и y для всех y ∈...
Меня интересует сортировка массива положительных целочисленных значений за линейное время (в модели оперативной памяти с одинаковой мерой стоимости, т. Е. Целые числа могут иметь размер до логарифмического, но предполагается, что арифметические операции над ними будут выполняться единица времени)....
Принцип 0-1 говорит, что если сеть сортировки работает для всех последовательностей 0-1, то она работает для любого набора чисел. Существует ли такое, что если сеть сортирует каждую последовательность 0-1 из S, то она сортирует каждую последовательность 0-1, а размер S является полиномиальным по n...
Мне нужно хранить наборы элементов типа а. Тип a частично упорядочен, поэтому сравнение и может вернуть меньшее, большее, равное или несопоставимое.2a1a1a_1a2a2a_2 Одна проблема с хеш-таблицами состоит в том, что два равных элемента могут быть представлены по-разному, и у меня нет доступа к...
Мне дают в качестве входных данных DAG из n вершин, где каждая вершина x дополнительно помечена некоторым S ( x ) ⊆ { 1 , … , nGGGnnnxxx .S(x)⊆{1,…,n}S(x)⊆{1,…,n}S(x) \subseteq \{1, \ldots, n\} Топологическим видом является биекция f из вершин G в { 1 , … , n } такая, что для всех x , y , если в G...
Пытаясь разработать собственный алгоритм сортировки, я ищу оптимальный эталон, с которым я могу его сравнить. Для несортированного порядка элементов A и отсортированного порядка B , какой эффективный способ вычислить оптимальное количество транспозиций, чтобы добраться от A до B ? Транспонирование...
Рассмотрим следующую настройку: нам дан стек который содержит элементов.sssnnn мы можем использовать постоянное количество дополнительных стеков .O(1)O(1)O(1) мы можем применить следующие операции к этим стекам: проверить, пуст ли стек, сравнить верхние позиции двух стеков, удалить верхний элемент...
Две части TCS - это алгоритмы и сложность. Я упрощенно скажу, что алгоритмы - это исследование верхних границ, показывающее, что вы можете что-то сделать (с заданными ограниченными ресурсами), а сложность заключается в том, чтобы показать, что вы не можете сделать это без каких-либо минимальных...
Я уже задавал этот вопрос на stackoverflow , но, возможно, он лучше подходит для этого сайта. Проблема в: У меня N пар целых чисел без знака. Мне нужно их отсортировать. Конечный вектор пар должен сортироваться неуклонно по первому числу в каждой паре и неуклонно по второму в каждой паре. Каждая...
Рассмотрим проблему, когда нам задают в качестве входных данных направленный ациклический граф G=(V,E)G=(V,E)G = (V, E) , функцию маркировки λλ\lambda из VVV в некоторый набор LLL с полным порядком...
У меня есть набор данных, который представляет собой ряд объектов, расположенных в двумерной сетке. Я знаю, что у меня строгий порядок, увеличивающийся по мере того, как вы идете слева направо в каждом ряду, и увеличивающийся сверху вниз в каждом столбце. Например, 1 2 3 4 6 7 5 8 9 Можно ли...