У меня вчера был этот вопрос на тесте Алгоритмов, и я не могу найти ответ. Это сводит меня с ума, потому что это стоило около 40 баллов. Я полагаю, что большинство класса не решило это правильно, потому что я не придумал решение за последние 24 часа.
Для произвольной двоичной строки длины n найдите три равномерно расположенные строки, если они существуют. Напишите алгоритм, который решает это за O (n * log (n)) время.
Таким образом, у строк, подобных этим, есть три "равномерно распределенных": 11100000, 0100100100.
редактировать: это случайное число, поэтому оно должно быть в состоянии работать для любого числа. Примеры, которые я привел, должны были проиллюстрировать «равномерно распределенное» свойство. Таким образом, 1001011 является действительным числом. С 1, 4 и 7 равными интервалами.
Ответы:
В заключение! Следуя указаниям в ответе sdcvvc , мы имеем его: алгоритм O (n log n) для задачи! Это тоже просто после того, как вы это поймете. Те, кто догадался, БПФ были правы.
Проблема: нам дана двоичная строка
S
длины n , и мы хотим найти в ней три равномерно распределенные единицы. Например,S
может быть110110010
, где n = 9. Оно равномерно расположено на 1 с в позициях 2, 5 и 8.Сканируйте
S
слева направо и составьте списокL
позиций из 1. ДляS=110110010
вышеизложенного у нас есть список L = [1, 2, 4, 5, 8]. Этот шаг O (n). Задача состоит в том, чтобы найти арифметическую прогрессию длины 3 вL
, то есть найти отличные a, b, c вL
таких, что ba = cb или, что эквивалентно, a + c = 2b . Для приведенного выше примера мы хотим найти прогрессию (2, 5, 8).Сделайте многочлен
p
с членами x k для каждого k вL
. Для приведенного выше примера мы сделаем многочлен p (x) = (x + x 2 + x 4 + x 5 + x 8 ) . Этот шаг O (n).Найдите многочлен
q
= p 2 , используя быстрое преобразование Фурье . Для приведенного выше примера мы получаем полином q (x) = x 16 + 2x 13 + 2x 12 + 3x 10 + 4x 9 + x 8 + 2x 7 + 4x 6 + 2x 5 + x 4 + 2x 3 + x 2 . Этот шаг O (n log n).Игнорировать все слагаемые, кроме тех, которые соответствуют x 2k для некоторого k in
L
. Для приведенного выше примера мы получаем термины x 16 , 3x 10 , x 8 , x 4 , x 2 . Этот шаг O (n), если вы решите сделать это вообще.Вот ключевой момент: коэффициент любого x 2b для b in
L
- это в точности количество пар (a, c) вL
таких, что a + c = 2b . [CLRS, Ex. 30.1-7] Одна такая пара (b, b) всегда (поэтому коэффициент равен по крайней мере 1), но если существует какая-либо другая пара (a, c) , то коэффициент равен по крайней мере 3 из (a, c) ) и (с, а) . Для приведенного выше примера мы имеем коэффициент х 10, равный 3 именно из-за AP (2,5,8). (Эти коэффициенты х 2bвсегда будет нечетным числом по причинам, указанным выше. И все остальные коэффициенты в q всегда будут четными.)Итак, алгоритм состоит в том, чтобы посмотреть на коэффициенты этих слагаемых x 2b и посмотреть, является ли какой-либо из них больше 1. Если их нет, то нет равномерно распределенных 1. Если это б в ,
L
для которых коэффициент х 2б больше 1, то мы знаем , что есть некоторая пара (а, с) - кроме (Ь, Ь) - для которых а + с = 2b . Чтобы найти фактическую пару, мы просто пробуем каждый a inL
(соответствующий c будет 2b-a ) и видим, есть ли 1 в позиции 2b-a inS
. Этот шаг O (n).Вот и все, ребята.
Кто-то может спросить: нужно ли нам использовать БПФ? Многие ответы, такие как бета , flybywire и rsp , предполагают, что подход, который проверяет каждую пару из 1 и видит, есть ли 1 в «третьей» позиции, может работать в O (n log n), основываясь на интуиции что если слишком много единиц, мы легко нашли бы тройку, а если слишком мало единиц, проверка всех пар занимает немного времени. К сожалению, в то время как эта интуиция является правильной и простым подходом является лучше , чем O (N 2 ), не намного лучше. Как и в ответе sdcvvc , мы можем взять «канторовоподобное множество» строк длиной n = 3 kс 1s в позициях, в которых в троичном представлении есть только 0s и 2s (no 1s). Такая строка имеет 2 k = n (log 2) / (log 3) ≈ n 0,63 единицы и не имеет равномерно распределенных 1 с, поэтому проверка всех пар будет иметь порядок квадрата числа 1 с: 4 k ≈ n 1,26, что, к сожалению, асимптотически намного больше, чем (n log n). На самом деле, худший случай еще хуже: Лео Мозер в 1953 году построил (эффективно) такие строки, которые имеют n 1-c / √ (log n) 1s, но не имеют равномерно распределенных 1s, что означает, что на таких строках простой подход занял бы Θ (n 2-2c / √ (log n) )- только крошечное немного лучше , чем Q (п 2 ) , удивительно!
О максимальном числе 1 в строке длиной n без 3 равномерно распределенных (что мы видели выше, было не менее n 0,63 от простой конструкции типа Кантора и не менее n 1-c / √ (log n) с Конструкция Мозера) - это OEIS A003002 . Он также может быть рассчитан непосредственно из OEIS A065825 как k, так что A065825 (k) ≤ n <A065825 (k + 1). Я написал программу для их поиска, и оказалось, что жадный алгоритм не дает самую длинную такую строку. Например, для n = 9 мы можем получить 5 1 с (110100011), но жадный дает только 4 (110110000), для n= 26 можно получить 11 1s (11001010001000010110001101) , но жадный дает только 8 (+11011000011011000000000000), а для п = 74 , мы можем получить 22 1s (11000010110001000001011010001000000000000000010001011010000010001101000011) , но жадный дает только 16 (11011000011011000000000000011011000011011000000000000000000000000000000000). Они согласны в довольно многих местах до 50 (например, все от 38 до 50), хотя. Как говорится в ссылках OEIS, кажется, что Ярослав Вроблевский заинтересован в этом вопросе, и он поддерживает веб-сайт об этих не усредняющих наборах . Точные цифры известны только до 194 года.
источник
Ваша проблема называется СРЕДНЯЯ в этой статье (1999):
Википедия :
Этого достаточно, чтобы решить вашу проблему :).
Что очень важно, так это то, что O (n log n) - это сложность с точки зрения количества нулей и единиц, а не количества единиц (которые могут быть заданы в виде массива, как [1,5,9,15]). Проверить, имеет ли набор арифметическую прогрессию, слагаемое числа 1, сложно, и согласно этой статье на 1999 год не известен более быстрый алгоритм, чем O (n 2 ), и предполагается, что он не существует. Все, кто не принимает это во внимание, пытаются решить открытую проблему.
Другая интересная информация, в основном неактуальная:
Нижняя граница:
Легкой нижней границей является канторовоподобное множество (числа 1..3 ^ n-1, не содержащие 1 в их троичном расширении) - его плотность равна n ^ (log_3 2) (около 0,631). Поэтому любой проверки, если набор не слишком большой, а затем проверка всех пар недостаточно для получения O (n log n). Вы должны исследовать последовательность умнее. Более нижняя граница указана здесь - это п 1-с / (журнал (п)) ^ (1/2) . Это означает, что набор Кантора не является оптимальным.
Верхняя граница - мой старый алгоритм:
Известно, что для больших n подмножество {1,2, ..., n}, не содержащее арифметической прогрессии, имеет не более n / (log n) ^ (1/20) элементов. Статья « О тройках в арифметической прогрессии» доказывает больше: набор не может содержать более n * 2 28 * (log log n / log n) 1/2 элементов. Таким образом, вы можете проверить, достигнута ли эта граница, а если нет, наивно проверить пары. Это алгоритм O (n 2 * log log n / log n), более быстрый, чем O (n 2 ). К сожалению, "На тройках ..." есть на Springer - но первая страница доступна, и изложение Бена Грина доступно здесь , страница 28, теорема 24.
Кстати, газеты принадлежат 1999 году - в том же году, что и первый, который я упомянул, поэтому, вероятно, первый не упоминает этот результат.
источник
Это не решение, а сходная точка зрения на то, что думал Алексей.
Я играл с созданием последовательностей с максимальным количеством единиц, и все они довольно интересны, я получил до 125 цифр, и вот первые 3 числа, которые он нашел, пытаясь вставить как можно больше «1» битов:
Обратите внимание, что все они фракталы (не слишком удивительно, учитывая ограничения). Может быть что-то в мышлении задом наперед, возможно, если строка не является фракталом с характеристикой, то она должна иметь повторяющуюся модель?
Спасибо бета за лучший термин для описания этих чисел.
Обновление: Увы, похоже, что шаблон ломается при запуске с достаточно большой начальной строки, например: 10000000000001:
источник
Я подозреваю, что простой подход, который выглядит как O (n ^ 2), на самом деле даст что-то лучше, например, O (n ln (n)). Последовательности, требующие наибольшего времени для тестирования (для любого заданного n), - это те, которые не содержат трио, и это накладывает серьезные ограничения на число единиц, которые могут быть в последовательности.
Я выдвинул несколько аргументов, размахивающих руками, но я не смог найти опрятного доказательства. Я собираюсь сделать удар в темноте: ответ - очень умная идея, которую профессор знал так долго, что это кажется очевидным, но это слишком сложно для студентов. (Или это, или вы проспали лекцию, которая покрывала это.)
источник
Редакция: 2009-10-17 23:00
Я запустил это на больших числах (например, строки 20 миллионов), и теперь я считаю, что этот алгоритм не O (n logn). Несмотря на это, это достаточно крутая реализация и содержит ряд оптимизаций, которые делают ее действительно быстрой. Он оценивает все расположения двоичных строк 24 или менее цифр менее чем за 25 секунд.
Я обновил код, чтобы включить
0 <= L < M < U <= X-1
наблюдение, сделанное ранее сегодня.оригинал
По сути, это похоже на другой вопрос, на который я ответил . Этот код также просматривал три значения в серии и определял, удовлетворяет ли триплет условию. Вот код C #, адаптированный из этого:
Принципиальные различия:
Этот код генерирует мощный набор данных, чтобы найти самый сложный вход для решения этого алгоритма.
Код предыдущего вопроса сгенерировал все решения с использованием генератора Python. Этот код просто отображает самое сложное для каждой длины шаблона.
Этот код проверяет расстояние от среднего элемента до его левого и правого края. Код Python проверял, была ли сумма выше или ниже 0.
Текущий код работает от середины к краю, чтобы найти кандидата. Код в предыдущей задаче работал от краев к середине. Это последнее изменение дает значительное улучшение производительности.
На основе наблюдений в конце этой записи код ищет пары четных чисел пар нечетных чисел, чтобы найти L и U, сохраняя M фиксированным. Это уменьшает количество поисков путем предварительного вычисления информации. Соответственно, код использует два уровня косвенности в основном цикле FindCandidate и требует двух вызовов FindCandidate для каждого среднего элемента: один раз для четных чисел и один раз для нечетных.
Общая идея состоит в том, чтобы работать с индексами, а не с необработанным представлением данных. Вычисление массива, в котором появляются единицы, позволяет алгоритму работать во времени, пропорциональном количеству единиц в данных, а не во времени, пропорциональном длине данных. Это стандартное преобразование: создайте структуру данных, которая позволит быстрее работать, сохраняя при этом эквивалентность задачи.
Результаты устарели: удалены.
Изменить: 2009-10-16 18:48
На данных yx, которым доверяют другие ответы как репрезентативные данные для вычисления, я получаю эти результаты ... Я удалил их. Они устарели.
Я хотел бы отметить, что эти данные не самые сложные для моего алгоритма, поэтому я считаю, что предположение о том, что фракталы yx труднее всего решить, ошибочно. Я ожидаю, что наихудший случай для конкретного алгоритма будет зависеть от самого алгоритма и вряд ли будет согласован для разных алгоритмов.
Изменить: 2009-10-17 13:30
Дальнейшие наблюдения по этому вопросу.
Сначала преобразуйте строку из 0 и 1 в массив индексов для каждой позиции 1. Скажем, длина этого массива A равна X. Тогда цель состоит в том, чтобы найти
такой, что
или
Поскольку A [L] и A [U] суммируются с четным числом, они не могут быть (четными, нечетными) или (нечетными, четными). Поиск совпадения можно улучшить, разбив A [] на нечетные и четные пулы и ища совпадения на A [M] в пулах нечетных и четных кандидатов по очереди.
Однако это скорее оптимизация производительности, чем алгоритмическое улучшение. Количество сравнений должно уменьшиться, но порядок алгоритма должен быть таким же.
Изменить 2009-10-18 00:45
Еще одна оптимизация происходит со мной в том же духе, что и разделение кандидатов на четных и нечетных. Поскольку три индекса нужно добавить к кратному 3 (a, a + x, a + 2x - mod 3 равно 0, независимо от a и x), вы можете разделить L, M и U на их значения mod 3 :
Фактически, вы можете объединить это с четным / нечетным наблюдением и разделить их на значения мод 6:
и так далее. Это обеспечило бы дальнейшую оптимизацию производительности, но не алгоритмическое ускорение.
источник
Пока не смог найти решение :(, но есть идеи.
Что если мы начнем с обратной задачи: построим последовательность с максимальным числом 1 с и БЕЗ любых равномерно распределенных трио. Если вы можете доказать, что максимальное число 1 равно o (n), то вы можете улучшить свою оценку, выполняя итерацию только по списку только 1.
источник
Это может помочь ....
Эта проблема сводится к следующему:
Например, для данной последовательности
[ 3, 5, 1, 3, 6, 5, 2, 2, 3, 5, 6, 4 ]
мы найдем подпоследовательность[ 3, 6, 5, 2, 2]
с префиксом[ 3, 6 ]
с префиксной суммой9
и с суффиксом[ 5, 2, 2 ]
с суффиксной суммой9
.Сокращение выглядит следующим образом:
Например, учитывая последовательность
[ 0, 1, 1, 0, 0, 1, 0, 0, 0, 1 0 ]
, мы бы нашли сокращение[ 1, 3, 4]
. Из этого сокращения мы вычисляем смежную подпоследовательность[ 1, 3, 4]
, префикс[ 1, 3]
с суммой4
и суффикс[ 4 ]
с суммой4
.Это сокращение может быть вычислено в
O(n)
.К сожалению, я не уверен, куда идти отсюда.
источник
Для простого типа задачи (т. Е. Вы ищете три «1» с единственным (т. Е. Ноль или более) «0» между ними), это довольно просто: вы можете просто разбить последовательность на каждое «1» и искать две смежные подпоследовательности, имеющие такой же длины (вторая подпоследовательность, конечно, не последняя). Очевидно, это можно сделать за O (n) раз.
Для более сложной версии (т. Е. Вы ищете индекс i и разрыв g > 0 такой, что
s[i]==s[i+g]==s[i+2*g]=="1"
), я не уверен, существует ли решение O (n log n) , поскольку возможно, что O (n²) триплетов, имеющих это свойство (представьте себе строку из всех, таких триплетов приблизительно n / 2 ). Конечно, вы ищете только один из них, но я не знаю, как его найти ...источник
Забавный вопрос, но как только вы поймете, что фактический шаблон между двумя единицами не имеет значения, алгоритм становится:
В коде, JTest fashion, (обратите внимание, этот код написан не для того, чтобы быть наиболее эффективным, и я добавил несколько println, чтобы увидеть, что происходит.)
источник
Я думал о подходе «разделяй и властвуй», который может сработать.
Во-первых, при предварительной обработке вам нужно вставить все числа, меньшие половины вашего размера ввода ( n / 3), в список.
Учитывая строку:
0000010101000100
(обратите внимание, что этот конкретный пример действителен)Вставьте все простые числа (и 1) от 1 до (16/2) в список: {1, 2, 3, 4, 5, 6, 7}
Затем разделите его пополам:
100000101 01000100
Продолжайте делать это, пока не доберетесь до строк размера 1. Для всех строк размера один с 1 в них добавьте индекс строки в список возможностей; в противном случае верните -1 в случае ошибки.
Вам также нужно будет вернуть список возможных расстояний, связанных с каждым начальным индексом. . в противном случае список включает в себя интервалы, которые должны быть исключены.
Итак, продолжаем с примером выше:
1000 0101 0100 0100
10 00 01 01 01 00 01 00
1 0 0 0 0 1 0 1 0 1 0 0 0 1 0 0
На первом шаге объединения у нас теперь восемь комплектов по два. Во-первых, у нас есть возможность множества, но мы узнаем, что интервал на 1 невозможен из-за присутствия другого нуля. Таким образом, мы возвращаем 0 (для индекса) и {2,3,4,5,7} за то, что интервал на 1 невозможен. Во втором у нас ничего нет и поэтому возвращаем -1. В третьем случае мы имеем совпадение без пропусков в индексе 5, поэтому возвращаем 5, {1,2,3,4,5,7}. В четвертой паре мы возвращаем 7, {1,2,3,4,5,7}. В пятом верните 9, {1,2,3,4,5,7}. В шестой верните -1. В седьмом верните 13, {1,2,3,4,5,7}. В восьмом верните -1.
Объединяя снова в четыре набора из четырех, мы имеем:
1000
: Return (0, {4,5,6,7})0101
: Return (5, {2,3,4,5,6,7}), (7, {1,2,3,4,5,6 , 7})0100
: Возврат (9, {3,4,5,6,7})0100
: Возврат (13, {3,4,5,6,7})Объединение в наборы из восьми:
10000101
: Return (0, {5,7}), (5, {2,3,4,5,6,7}), (7, {1,2,3,4,5,6,7})01000100
: Возврат (9, {4,7}), (13, {3,4,5,6,7})Объединение в набор из шестнадцати:
10000101 01000100
По мере нашего продвижения, мы продолжаем проверять все возможности до сих пор. До этого шага мы оставили вещи, которые выходили за пределы конца строки, но теперь мы можем проверить все возможности.
По сути, мы проверяем первые 1 с интервалами 5 и 7 и обнаруживаем, что они не совпадают с 1. (Обратите внимание, что каждая проверка является ПОСТОЯННОЙ, а не линейным временем) Затем мы проверяем вторую (индекс 5) с интервалами 2, 3, 4, 5, 6 и 7 - или мы бы это сделали, но мы можем остановиться на 2, так как это на самом деле совпадает.
Уф! Это довольно длинный алгоритм.
Я не знаю 100%, если это O (n log n) из-за последнего шага, но, насколько я могу судить , все, что там есть, определенно O (n log n) . Я вернусь к этому позже и попытаюсь уточнить последний шаг.
РЕДАКТИРОВАТЬ: изменил мой ответ, чтобы отразить комментарий Велбога. Извините за ошибку. Я также напишу немного псевдокода позже, когда у меня будет немного больше времени, чтобы расшифровать то, что я написал снова. ;-)
источник
100010001
? Если я правильно понимаю ваш подход, он не сможет соответствовать, потому что правильный ответ(0,{4})
невозможно вычислить. Учитывая, что в вашем списке нужны непростые числа, легко придумать патологические строки, которые раздувают списки возможностей, которые вам нужно проверить выше O (n log (n)), я думаю.Здесь я приведу приблизительное предположение и позволю тем, кто лучше разбирается в сложности, помочь мне понять, как мой алгоритм работает в O-нотации.
Я не знаю, как рассчитать сложность для этого, кто-нибудь может помочь?
редактировать: добавить код, чтобы проиллюстрировать мою идею
edit2: попытался скомпилировать мой код и обнаружил некоторые серьезные ошибки, исправлено
источник
Я придумал что-то вроде этого:
Это вдохновлено andycjw.
Что касается сложности, то это может быть O (nlogn), так как в каждой рекурсии мы делим на два.
Надеюсь, поможет.
источник
Хорошо, я собираюсь сделать еще один удар по проблеме. Я думаю, что могу доказать алгоритм O (n log (n)), который похож на те, которые уже обсуждались, используя сбалансированное двоичное дерево для хранения расстояний между единицами. Этот подход был вдохновлен наблюдением Джастиса о сокращении проблемы до списка расстояний между единицами.
Можем ли мы отсканировать входную строку, чтобы построить сбалансированное двоичное дерево вокруг позиции 1, чтобы каждый узел сохранял позицию 1, а каждое ребро обозначалось расстоянием до смежной 1 для каждого дочернего узла. Например:
Это может быть сделано в O (n log (n)), поскольку для строки размера n каждая вставка принимает O (log (n)) в худшем случае.
Тогда проблема заключается в поиске дерева, чтобы определить, есть ли на каком-либо узле путь от этого узла до левого потомка, который имеет то же расстояние, что и путь через правый потомок. Это можно сделать рекурсивно на каждом поддереве. При объединении двух поддеревьев в поиске мы должны сравнить расстояния от путей в левом поддереве с расстояниями от путей в правом. Поскольку число путей в поддереве будет пропорционально log (n), а количество узлов равно n, я считаю, что это можно сделать за O (n log (n)).
Я что-то пропустил?
источник
Это казалось забавной проблемой, поэтому я решил попробовать свои силы в этом.
Я делаю предположение, что 111000001 найдет первые 3 и будет успешным. По сути, число нулей, следующих за 1, является важным, поскольку, согласно вашему определению, 0111000 совпадает с 111000. Как только вы найдете два случая 1, следующий найденный 1 завершает трилогию.
Вот это в Python:
Это первая попытка, так что я уверен, что это можно написать более понятным способом. Пожалуйста, перечислите случаи, когда этот метод не работает внизу.
источник
Я предполагаю, что причина этого nlog (n) заключается в следующем:
Итак, у вас есть n, log (n) и 1 ... O (nlogn)
Редактировать: Ой, мой плохой. В моем мозгу было установлено, что n / 2 было logn ... чего, очевидно, нет (удвоение числа элементов по-прежнему удваивает число итераций во внутреннем цикле). Это все еще на п ^ 2, не решая проблему. Ну, по крайней мере, я должен написать код :)
Реализация в Tcl
источник
Я думаю, что нашел способ решения проблемы, но я не могу построить формальное доказательство. Решение, которое я принял, написано на Java и использует счетчик 'n' для подсчета количества обращений к списку / массиву. Так что n должно быть меньше или равно stringLength * log (stringLength), если это правильно. Я пробовал это для чисел от 0 до 2 ^ 22, и это работает.
Он начинается с перебора входной строки и составления списка всех индексов, которые содержат единицу. Это просто O (n).
Затем из списка индексов он выбирает firstIndex и secondIndex, который больше первого. Эти два индекса должны содержать индексы, потому что они находятся в списке индексов. Оттуда может быть рассчитан третий индекс. Если inputString [thirdIndex] равен 1, то он останавливается.
}
дополнительное примечание: счетчик n не увеличивается, когда он перебирает входную строку для построения списка индексов. Эта операция O (n), поэтому она не повлияет на сложность алгоритма.
источник
O(n^2)
алгоритм.Один из путей решения этой проблемы - думать о факторах и изменениях.
При сдвиге вы сравниваете строку единиц и нулей со сдвинутой версией самого себя. Затем вы берете соответствующие. Возьмем этот пример, сдвинутый на два:
Результирующие 1 (побитовые AND) должны представлять все те 1, которые равномерно разделены двумя. Тот же пример сдвинут на три:
В этом случае нет 1, которые равномерно распределены на три.
Так что это говорит вам? Хорошо, что вам нужно только проверить сдвиги, которые являются простыми числами. Например, скажем, у вас есть два 1, которые шесть друг от друга. Вам нужно будет только проверить «две» смены и «три» смены (поскольку они делят шесть). Например:
Таким образом, единственные сдвиги, которые вам когда-либо нужно проверять, это 2,3,5,7,11,13 и т. Д. До простого, ближайшего к квадратному корню, размера строки цифр.
Почти решен?
Я думаю, что я ближе к решению. В принципе:
Я думаю, что самый большой ключ к ответу - это то, что самые быстрые алгоритмы сортировки - это O (n * log (n)).
НЕПРАВИЛЬНО
Шаг 1 не так, как указал коллега. Если бы у нас были единицы в позициях 2, 12 и 102. Тогда, взяв модуль 10, они все имели бы одинаковые остатки, и все же не были бы одинаково разнесены! Сожалею.
источник
Вот несколько мыслей, которые, несмотря на все мои старания, не обернутся в поклон. Тем не менее, они могут быть полезной отправной точкой для чьего-либо анализа.
Рассмотрим предложенное решение следующим образом. Это тот подход, который предложили несколько человек, включая меня в предыдущей версии этого ответа.
:)
Теперь рассмотрим строки входных строк, подобные приведенным ниже, которые не будут иметь решения:
В общем, это конкатенация k строк вида j 0, за которыми следует 1 для j от нуля до k-1.
Обратите внимание, что длины подстрок равны 1, 2, 3 и т. Д. Итак, размер задачи n имеет подстроки длиной от 1 до k такие, что n = k (k + 1) / 2.
Обратите внимание, что k также отслеживает количество единиц, которые мы должны рассмотреть. Помните, что каждый раз, когда мы видим 1, нам нужно учитывать все 1, увиденные до сих пор. Поэтому, когда мы видим вторую 1, мы рассматриваем только первую, когда мы видим третью 1, мы пересматриваем первые две, когда мы видим четвертую 1, нам нужно пересматривать первые три, и так далее. К концу алгоритма мы рассмотрели k (k-1) / 2 пары единиц. Назовите это р.
Соотношение между n и p таково, что n = p + k.
Процесс прохождения строки занимает O (n) времени. Каждый раз, когда встречается 1, выполняется максимум (k-1) сравнений. Поскольку n = k (k + 1) / 2, n> k ** 2, то sqrt (n)> k. Это дает нам O (n sqrt (n)) или O (n ** 3/2). Тем не менее, обратите внимание, что это не может быть очень жесткой границей, потому что число сравнений идет от 1 до максимум k, это не k за все время. Но я не уверен, как объяснить это в математике.
Это все еще не O (n log (n)). Кроме того, я не могу доказать, что эти данные являются худшими, хотя я подозреваю, что это так. Я думаю, что более плотная упаковка 1 в передней части приводит к еще более редкой упаковке в конце.
Поскольку кто-то может все еще найти это полезным, вот мой код для этого решения на Perl:
источник
При сканировании 1 с, добавьте их позиции в список. При добавлении второй и последующих 1, сравните их до сих пор с каждой позицией в списке. Интервал равен currentOne (в центре) - previousOne (слева). Правый бит - currentOne + интервал. Если это 1, конец.
Список из них растет обратно пропорционально расстоянию между ними. Проще говоря, если у вас много нулей между 1 (как в худшем случае), ваш список известных 1 будет расти довольно медленно.
источник
Я решил добавить один комментарий, прежде чем публиковать 22-е наивное решение проблемы. Для наивного решения нам не нужно показывать, что число единиц в строке не больше O (log (n)), а скорее всего O (sqrt (n * log (n))).
Решение:
По сути, это довольно похоже на идею и реализацию flybywire, хотя и смотрит вперед, а не назад.
Жадный струнный строитель:
(В свою защиту, я все еще нахожусь в стадии понимания "учить питона")
Кроме того, потенциально полезный вывод из жадного построения строк, есть довольно последовательный скачок после попадания степени 2 в число 1 ... которого я не хотел ждать, чтобы засвидетельствовать попадание в 2096.
источник
Я постараюсь представить математический подход. Это скорее начало, чем конец, поэтому любая помощь, комментарии или даже противоречия будут высоко оценены. Однако, если такой подход доказан - алгоритм представляет собой простой поиск в строке.
Для фиксированного числа пробелов
k
и строкиS
поиск k-пространственного триплета занимаетO(n)
- мы просто проверяем каждое0<=i<=(n-2k)
ifS[i]==S[i+k]==S[i+2k]
. Тест проходит,O(1)
и мы делаем этоn-k
раз, гдеk
есть константа, поэтому она принимаетO(n-k)=O(n)
.Давайте предположим, что существует обратная пропорция между числом
1
's' и максимальным пространством, которое мы должны искать. То есть, если их много1
, должен быть триплет, и он должен быть достаточно плотным; Если их всего несколько1
, триплет (если есть) может быть довольно разреженным. Другими словами, я могу доказать, что если мне достаточно1
, такой триплет должен существовать - и чем больше1
у меня, тем более плотный триплет должен быть найден. Это может быть объяснено принципом Pigeonhole - Надеюсь уточнить это позже.Скажем, есть верхняя граница
k
возможного количества пробелов, которые я должен искать. Теперь для каждого1
расположенного вS[i]
нам нужно проверить1
вS[i-1]
иS[i+1]
,S[i-2]
иS[i+2]
, ...,S[i-k]
иS[i+k]
. Это требуетсяO((k^2-k)/2)=O(k^2)
для каждого1
вS
- из-за формулы суммирования серии Гаусса . Обратите внимание, что это отличается от раздела 1 - я имеюk
в качестве верхней границы для числа пробелов, а не как постоянный пробел.Нам нужно доказать
O(n*log(n))
. То есть нам нужно показать, чтоk*(number of 1's)
пропорциональноlog(n)
.Если мы можем сделать это, алгоритм тривиален - для каждого
1
вS
чей индексi
, просто искать1
«S с каждой стороны до расстоянияk
. Если два были найдены на одном расстоянии, вернитеi
иk
. Опять же, сложная часть будет найтиk
и доказать правильность.Буду очень признателен за ваши комментарии здесь - я пытался найти связь между
k
числом и числом1
на моей доске, но пока безуспешно.источник
Предположение:
Просто неправильно, говоря о log (n) числе верхнего предела единиц
РЕДАКТИРОВАТЬ:
Теперь я обнаружил, что используя числа Кантора (если они верны), плотность на множестве равна (2/3) ^ Log_3 (n) (что за странная функция), и я согласен, плотность log (n) / n слишком сильная.
Если это верхний предел, существует алгоритм, который решает эту проблему по крайней мере за O (n * (3/2) ^ (log (n) / log (3))) сложность времени и O ((3/2) ^ ( log (n) / log (3))) сложность пространства. (проверьте ответ юстиции для algorhitm)
Это все еще намного лучше, чем O (n ^ 2)
Эта функция ((3/2) ^ (log (n) / log (3))) действительно выглядит как n * log (n) на первый взгляд.
Как я получил эту формулу?
Наложение числа Кантора на строку.
Предположим, что длина строки равна 3 ^ p == n.
На каждом шаге генерации строки Кантора вы сохраняете 2/3 преобладающего числа единиц. Примените это р раз.
Это означает (n * ((2/3) ^ p)) -> (((3 ^ p)) * ((2/3) ^ p)) оставшихся и после упрощения 2 ^ p. Это означает 2 ^ p единиц в 3 ^ p строке -> (3/2) ^ p единиц. Подставьте p = log (n) / log (3) и получите
((3/2) ^ (log (n) / log (3)))
источник
Как насчет простого решения O (n) с пространством O (n ^ 2)? (Используется предположение, что все побитовые операторы работают в O (1).)
Алгоритм в основном работает в четыре этапа:
Этап 1: для каждого бита в вашем исходном числе выясните, как далеко они находятся, но примите во внимание только одно направление. (Я рассмотрел все биты в направлении младшего значащего бита.)
Этап 2: обратный порядок битов на входе;
Этап 3: повторите шаг 1 на обратном входе.
Стадия 4: Сравните результаты Стадии 1 и Стадии 3. Если какие-либо биты расположены на одинаковом расстоянии выше И ниже, мы должны получить попадание.
Имейте в виду, что ни один шаг в вышеприведенном алгоритме не занимает больше времени, чем O (n). ^ _ ^
В качестве дополнительного преимущества этот алгоритм найдет ВСЕ одинаково расположенные из КАЖДОГО числа. Так, например, если вы получите результат «0x0005», то в равном расстоянии 1 и 3 единицы
Я действительно не пытался оптимизировать код ниже, но это компилируемый код C #, который, кажется, работает.
Кто-то, вероятно, прокомментирует, что для любого достаточно большого числа битовые операции не могут быть выполнены в O (1). Ты был бы прав. Тем не менее, я бы предположил, что каждое решение, которое использует сложение, вычитание, умножение или деление (что не может быть сделано путем сдвига) также будет иметь эту проблему.
источник
Ниже приведено решение. Там и там могут быть небольшие ошибки, но идея здравая.
Редактировать: это не n * log (n)
КОД ПСЕВДО:
Код C #:
Как это устроено:
источник
Очевидно, что нам нужно по крайней мере проверять связки триплетов одновременно, поэтому нам нужно как-то сжать проверки. У меня есть алгоритм-кандидат, но анализ сложности времени выходит за рамки моих возможностей * временной порог.
Постройте дерево, в котором у каждого узла есть три дочерних элемента, и каждый узел содержит общее количество единиц на своих листьях. Построить связанный список на 1, а также. Назначьте каждому узлу разрешенную стоимость, пропорциональную диапазону, который он охватывает. Пока время, которое мы проводим в каждом узле, находится в пределах бюджета, у нас будет алгоритм O (n lg n).
-
Начните с корня. Если квадрат от общего числа 1 ниже, чем его разрешенная стоимость, примените наивный алгоритм. В противном случае рециркулировать на своих детей.
Теперь мы либо вернулись в рамках бюджета, либо знаем, что в одном из дочерних элементов нет действительных триплетов. Поэтому мы должны проверить триузлы между узлами.
Теперь все становится невероятно грязным. По сути, мы хотим использовать потенциальные наборы детей, ограничивая диапазон. Как только диапазон достаточно ограничен, чтобы наивный алгоритм работал в рамках бюджета, вы делаете это. Наслаждайтесь реализацией этого, потому что я гарантирую, что это будет утомительно. Там как десяток дел.
-
Причина, по которой я думаю, что алгоритм будет работать, состоит в том, что последовательности без действительных триплетов, кажется, чередуются между группами 1 и партиями 0. Он эффективно разделяет близлежащее пространство поиска, и дерево имитирует это разбиение.
Время выполнения алгоритма совсем не очевидно. Он опирается на нетривиальные свойства последовательности. Если 1 действительно редки, то наивный алгоритм будет работать в рамках бюджета. Если 1 плотные, то совпадение должно быть найдено сразу. Но если плотность «просто правильная» (например, около ~ n ^ 0,63, чего можно добиться, установив все биты в позиции без цифры «2» в базе 3), я не знаю, будет ли это работать. Вы должны доказать, что эффект расщепления достаточно силен.
источник
Никакого теоретического ответа здесь нет, но я написал быструю Java-программу для изучения поведения во время выполнения в зависимости от k и n, где n - общая длина бита, а k - число единиц. Я с несколькими из ответчиков, которые говорят, что «обычный» алгоритм, который проверяет все пары позиций битов и ищет 3-й бит, хотя для этого потребуется O (k ^ 2) в худшем случае, в реальность, потому что в худшем случае нужны разреженные цепочки битов, это O (n ln n).
В любом случае, вот программа, ниже. Это программа в стиле Монте-Карло, которая запускает большое количество испытаний NTRIALS для константы n и случайным образом генерирует наборы битов для диапазона значений k, используя процессы Бернулли с ограничениями плотности единиц, которые могут быть заданы, и записывает время выполнения. найти или не найти триплет из равномерно распределенных, время измеряется в шагах, а не во времени ЦП. Я запустил его для n = 64, 256, 1024, 4096, 16384 * (все еще выполняется), сначала тестовый прогон с 500000 испытаний, чтобы увидеть, какие значения k занимают самое продолжительное время работы, затем другой тест с 5000000 тестами с суженными- сосредоточиться на плотности, чтобы увидеть, как эти значения выглядят. Самые длинные времена пробега случаются с очень разреженной плотностью (например, для n = 4096 пики времени пробега находятся в диапазоне k = 16-64, с небольшим пиком для среднего времени пробега при 4212 шагах при k = 31, максимальное время выполнения достигло максимума при 5101 шагах при k = 58). Похоже, что для шага O (k ^ 2) в худшем случае потребовалось бы чрезвычайно большое значение N, чтобы стать больше шага O (n), когда вы сканируете цепочку битов, чтобы найти индексы позиции 1.
источник
У меня проблемы с наихудшими сценариями с миллионами цифр. По
/dev/urandom
сути, размытость дает O (n), но я знаю, что худший случай хуже этого. Я просто не могу сказать, насколько хуже. Для малого достаточноn
просто найти входные данные3*n*log(n)
, но на удивление трудно отличить их от какого-то другого порядка роста для этой конкретной проблемы.Может ли кто-нибудь, кто работал с входными данными для наихудшего случая, генерировать строку с длиной, скажем, сто тысяч?
источник
Адаптация алгоритма Рабина-Карпа может быть возможной для вас. Его сложность равна 0 (n), поэтому он может вам помочь.
Посмотрите http://en.wikipedia.org/wiki/Rabin-Karp_string_search_algorithm
источник
Может ли это быть решением? Я не уверен, что это O (nlogn), но, на мой взгляд, это лучше, чем O (n²), потому что единственный способ не найти тройку - это распределение простых чисел.
Есть место для улучшения, второй найденный 1 может быть следующим первым 1. Также нет проверки ошибок.
источник
Я думаю, что этот алгоритм имеет O (n log n) сложности (C ++, DevStudio 2k5). Теперь я не знаю деталей того, как анализировать алгоритм, чтобы определить его сложность, поэтому я добавил в код некоторую информацию для сбора метрик. Код подсчитывает количество тестов, выполненных в последовательности 1 и 0 для любого заданного ввода (надеюсь, я не сделал шарики алгоритма). Мы можем сравнить фактическое количество тестов со значением O и посмотреть, есть ли корреляция.
Эта программа выводит количество тестов для каждой строки длиной до 32 символов. Вот результаты:
Я также добавил значения 'n log n'. Нанесите их на график с помощью выбранного графического инструмента, чтобы увидеть корреляцию между двумя результатами. Распространяется ли этот анализ на все значения n? Я не знаю.
источник