Алгоритм O (nlogn) - Найти три равномерно расположенных в двоичной строке

Question

У меня вчера был этот вопрос на тесте Алгоритмов, и я не могу найти ответ. Это сводит меня с ума, потому что это стоило около 40 баллов. Я полагаю, что большинство класса не решило это правильно, потому что я не придумал решение за последние 24 часа.

Учитывая произвольную двоичную строку длины n, найдите три равномерно распределенные строки внутри строки, если они существуют. Напишите алгоритм, который решает это за время O (n * log (n)).

Таким образом, у подобных строк есть три "равномерно распределенных": 11100000, 0100100100

edit: это случайное число, поэтому оно должно работать на любое число. Примеры, которые я привел, должны были проиллюстрировать «равномерно распределенное» свойство. Таким образом, 1001011 является действительным числом. 1, 4 и 7 равны друг другу.

Answer 1

Наконец-то! Следуя указаниям в ответе sdcvvc , мы имеем его: алгоритм O (n log n) для задачи! Это тоже просто после того, как вы это поймете. Те, кто угадал БПФ, были правы.

Проблема: нам дана двоичная строка S длины n , и мы хотим найти в ней три равномерно распределенные единицы. Например, S может быть 110110010, где n = 9. Оно равномерно расположено на 1 с в позициях 2, 5 и 8.

1. Сканирование 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).

2. Создайте полином p с условиями x ^k для каждого k в L. Для приведенного выше примера мы делаем полином p (x) = (x + x ² + x ⁴ + x ⁵ + x ⁸ ) . Этот шаг O (n).

3. Найдите полином q = p ² , используя Быстрое преобразование Фурье . Для приведенного выше примера мы получаем полином q (x) = x ¹⁶ + 2x ¹³ + 2x ¹² + 3x ¹⁰ + 4x ⁹ + x ⁸ + 2x ⁷ + 4x ⁶ + 2x ⁵ + x ⁴ + 2x ³ + x ² . Этот шаг O (n log n).

4. Игнорировать все термины, кроме тех, которые соответствуют x ^2k для некоторых k в L. Для приведенного выше примера мы получаем условия x ¹⁶ , 3x ¹⁰ , x ⁸ , x ⁴ , x ² . Этот шаг O (n), если вы решите сделать это вообще.

Вот критический момент: коэффициент любого x ^2b для b в L равен точно количество пар (a, c) в L, так что a + c = 2b . [CLRS, Ex. 30.1-7] Одна такая пара: (b, b) всегда (поэтому коэффициент равен не менее 1), но если существует какая-либо другая пара (a, c) , то коэффициент составляет не менее 3: (a, c) и (c, a) . Для приведенного выше примера мы имеем коэффициент x ¹⁰ , равный 3 именно из-за AP (2,5,8). (Эти коэффициенты x ^2b всегда будут нечетными числами по причинам, указанным выше. И все остальные коэффициенты в q всегда будут четными.)

Итак, алгоритм состоит в том, чтобы посмотреть на коэффициенты этих слагаемых x ^2b и посмотреть, больше ли один из них, чем 1. Если их нет, то не равны 1 с. Если равно a b в L, для которого коэффициент x ^2b больше 1, то мы знаем, что некоторая пара (a, c) - отличная от (b, b) - для которой a + c = 2b . Чтобы найти фактическую пару, мы просто попробуем каждый a в L (соответствующий c будет 2b-a ) и посмотрим, есть ли 1 в положении 2b-a в S. Этот шаг O (n).

Вот и все, ребята.

---

Кто-то может спросить: нужно ли нам использовать БПФ? Многие ответы, такие как бета , flybywire и rsp , предполагают, что подход, который проверяет каждую пару единиц 1 и определяет, есть ли 1 на " третья позиция может работать в O (n log n), основываясь на интуиции, что если слишком много 1, мы легко найдем тройку, а если слишком мало 1, проверка всех пар займет немного времени. К сожалению, хотя эта интуиция верна и простой подход на лучше, чем O (n ² ), он не намного лучше. Как и в ответе sdcvvc , мы можем взять «канторовоподобный набор» строк длиной n = 3 ^k , с единицами в позициях, троичное представление которых имеет только 0 и 2 (без 1). Такая строка содержит 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)} 1 в них, но нет равномерно распределенных 1, что означает, что для таких строк простой подход будет принимать Θ (n ^{2-2c / √ (log n)} ) - только a крошечный немного лучше, чем Θ (n ² ) , на удивление!

---

О максимальном числе 1 в строке длиной n без 3 равномерно распределенных (мы видели выше, было не менее n ^0,63 из простой конструкции типа Кантора и как минимум n ^{1-c / √ (log n)} в конструкции Мозера) - это OEIS A003002 . Он также может быть рассчитан непосредственно из OEIS A065825 как k, так что A065825 (k) ≤ n не дает самую длинную такую ​​строку. Например, для n = 9 мы можем получить 5 1 с (110100011), но жадный дает только 4 (110110000), для n = 26 мы можем получить 11 1 с (11001010001000010110001101) но жадный дает только 8 (11011000011011000000000000), а для n = 74 мы можем получить 22 1с (1100001011000100000101101000100000000000000000001011010000010001101000011), но жадный дает только 16 (1101100000000000000000000000101) Они согласны в довольно многих местах до 50 (например, все от 38 до 50), хотя. Как говорится в ссылках OEIS, кажется, что Ярослав Вроблевский интересуется этим вопросом, и он поддерживает веб-сайт по этим неусредняющим наборам . Точные цифры известны только до 194.

Answer 2

Ваша проблема называется СРЕДНЕГО в этой статье (1999):

Задача является 3SUM-сложной, если есть субквадратичное сокращение из задачи 3SUM: При заданном множестве A из n целых чисел существуют ли элементы a, b, c в A, такие что a + b + c = 0? Не известно, является ли AVERAGE 3SUM-сложным. Тем не менее, существует простое линейное сокращение времени от AVERAGE до 3SUM, описание которого мы опускаем.

Википедия

Когда целые числа находятся в диапазоне [-u ... u], 3SUM может быть решена за время O (n + u lg u) путем представления S как битового вектора и выполнения свертки с использованием FFT.

Этого достаточно, чтобы решить вашу проблему:).

Что очень важно, так это то, что O (n log n) представляет собой сложность с точки зрения количества нулей и единиц, а не количества единиц (которые могут быть заданы в виде массива, например [1, 5,9,15]). Проверять, имеет ли набор арифметическую прогрессию, слагаемое числа 1, сложно, и согласно этому документу по состоянию на 1999 год не известен более быстрый алгоритм, чем O (n ² ), и предполагается, что он не не существует Все, кто не принимает это во внимание, пытаются решить открытую проблему.

Другая интересная информация, в основном неактуальная:

Нижняя граница:

Легкой нижней границей является канторовоподобное множество (числа 1..3 ^ n-1, не содержащее 1 в их троичном расширении) - его плотность равна n ^ (log_3 2) (около 0,631). Поэтому любой проверки, если набор не слишком большой, а затем проверка всех пар недостаточно, чтобы получить O (n log n). Вы должны исследовать последовательность умнее. Лучшая нижняя граница указана здесь - это n ^{1-c / (log (n)) ^ (1/2)} . Это означает, что набор Кантора не оптимален.

Верхняя граница - мой старый алгоритм:

Известно, что для больших n подмножество {1,2, ..., n}, не содержащее арифметическую прогрессию, имеет не более n / (log n) ^ (1/20) элементов. Статья О тройках в арифметической прогрессии доказывает больше: набор не может содержать более n * 2 ²⁸ * (log log n / log n) ^1/2 элементы. Таким образом, вы можете проверить, достигнута ли эта граница, а если нет, наивно проверить пары. Это алгоритм O (n ² * log log n / log n), более быстрый, чем O (n ² ). К сожалению, "На тройках ..." есть на Springer - но первая страница доступна, и экспозиция Бена Грина доступна здесь , страница 28, теорема 24.

Кстати, газеты принадлежат 1999 году - в том же году, что и первый, о котором я упоминал, поэтому, вероятно, поэтому первый не упоминает этот результат.

Answer 3

Это не решение, а сходство с тем, о чем Алексей думал

Я играл с созданием последовательностей с максимальным количеством единиц, и все они довольно интересны, я получил до 125 цифр, и вот первые 3 числа, которые он нашел, пытаясь вставить как можно больше битов «1» :

• 11011000011011000000000000001101100001101100000000000000000000000000000000000000000110110000110110000000000000011011000011011
• 10110100010110100000000000010110100010110100000000000000000000000000000000000000000101101000101101000000000000101101000101101
• 10011001010011001000000000010011001010011001000000000000000000000000000000000000010011001010011001000000000010011001010011001

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

Спасибо бета за лучший термин для описания этих чисел.

Обновление: Увы, похоже, что шаблон ломается при запуске с достаточно большой начальной строки, например: 10000000000001:

100000000000011
10000000000001101
100000000000011011
10000000000001101100001
100000000000011011000011
10000000000001101100001101
100000000000011011000011010000000001
100000000000011011000011010000000001001
1000000000000110110000110100000000010011
1000000000000110110000110100000000010011001
10000000000001101100001101000000000100110010000000001
10000000000001101100001101000000000100110010000000001000001
1000000000000110110000110100000000010011001000000000100000100000000000001
10000000000001101100001101000000000100110010000000001000001000000000000011
1000000000000110110000110100000000010011001000000000100000100000000000001101
100000000000011011000011010000000001001100100000000010000010000000000000110100001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001
1000000000000110110000110100000000010011001000000000100000100000000000001101000010010000010000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001
1000000000000110110000110100000000010011001000000000100000100000000000001101000010010000010000001100010000000010000000000000000000000000000000000000000100000010000000000000011
1000000000000110110000110100000000010011001000000000100000100000000000001101000010010000010000001100010000000010000000000000000000000000000000000000000100000010000000000000011000000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000011
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000011000001
1000000000000110110000110100000000010011001000000000100000100000000000001101000010010000010000001100010000000010000000000000000000000000000000000000000100000010000000000000011000000001100100000000100100000000000010000000010000100000100100010010000010000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000110000010000000000000000000001
1000000000000110110000110100000000010011001000000000100000100000000000001101000010010000010000001100010000000010000000000000000000000000000000000000000100000010000000000000011000000001100100000000100100000000000010000000010000100000100100010010000010000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000110000010000000000000000000001001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000001100000100000000000000000000010010000000000000000000000000000000000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000011000001000000000000000000000100100000000000000000000000000000000000011
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000011000001000000000000000000000100100000000000000000000000000000000000011001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000001100000100000000000000000000010010000000000000000000000000000000000001100100000000000000000000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000001100000100000000000000000000010010000000000000000000000000000000000001100100000000000000000000001001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000001100000100000000000000000000010010000000000000000000000000000000000001100100000000000000000000001001000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000011000001000000000000000000000100100000000000000000000000000000000000011001000000000000000000000010010000010000001
1000000000000110110000110100000000010011001000000000100000100000000000001101000010010000010000001100010000000010000000000000000000000000000000000000000100000010000000000000011000000001100100000000100100000000000010000000010000100000100100010010000010000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000110000010000000000000000000001001000000000000000000000000000000000000110010000000000000000000000100100000100000011
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000001100000100000000000000000000010010000000000000000000000000000000000001100100000000000000000000001001000001000000110000000000001

Answer 4

Я подозреваю, что простой подход, который выглядит как O (n ^ 2), на самом деле даст что-то лучше, например O (n ln (n)). Последовательности, требующие наибольшего времени для тестирования (для любого заданного n), - это те, которые не содержат трио, и это накладывает жесткие ограничения на число единиц, которые могут быть в последовательности.

Я выдвинул несколько аргументов, размахивающих руками, но я не смог найти опрятного доказательства. Я собираюсь сделать удар в темноте: ответ - очень умная идея, которую профессор знал так долго, что это кажется очевидным, но это слишком сложно для студентов. (Либо это, либо вы проспали лекцию, которая освещала это.)

Answer 5

Редакция: 2009-10-17 23: 00

Я запустил это на больших числах (например, строки 20 миллионов), и теперь я считаю, что этот алгоритм не O (n logn). Несмотря на это, это достаточно классная реализация и содержит ряд оптимизаций, которые делают ее действительно быстрой. Он оценивает все расположения двоичных строк 24 или менее цифр менее чем за 25 секунд.

Я обновил код для включения наблюдения 0 <= L < M < U <= X-1, сделанного ранее сегодня.

---

Оригинал

В принципе, это похоже на другой вопрос, на который я ответил . Этот код также просматривал три значения в серии и определял, удовлетворяет ли триплет условию. Вот код C #, адаптированный из этого:

using System;
using System.Collections.Generic;

namespace StackOverflow1560523
{
    class Program
    {
        public struct Pair<T>
        {
            public T Low, High;
        }
        static bool FindCandidate(int candidate, 
            List<int> arr, 
            List<int> pool, 
            Pair<int> pair, 
            ref int iterations)
        {
            int lower = pair.Low, upper = pair.High;
            while ((lower >= 0) && (upper < pool.Count))
            {
                int lowRange = candidate - arr[pool[lower]];
                int highRange = arr[pool[upper]] - candidate;
                iterations++;
                if (lowRange < highRange)
                    lower -= 1;
                else if (lowRange > highRange)
                    upper += 1;
                else
                    return true;
            }
            return false;
        }
        static List<int> BuildOnesArray(string s)
        {
            List<int> arr = new List<int>();
            for (int i = 0; i < s.Length; i++)
                if (s[i] == '1')
                    arr.Add(i);
            return arr;
        }
        static void BuildIndexes(List<int> arr, 
            ref List<int> even, ref List<int> odd, 
            ref List<Pair<int>> evenIndex, ref List<Pair<int>> oddIndex)
        {
            for (int i = 0; i < arr.Count; i++)
            {
                bool isEven = (arr[i] & 1) == 0;
                if (isEven)
                {
                    evenIndex.Add(new Pair<int> {Low=even.Count-1, High=even.Count+1});
                    oddIndex.Add(new Pair<int> {Low=odd.Count-1, High=odd.Count});
                    even.Add(i);
                }
                else
                {
                    oddIndex.Add(new Pair<int> {Low=odd.Count-1, High=odd.Count+1});
                    evenIndex.Add(new Pair<int> {Low=even.Count-1, High=even.Count});
                    odd.Add(i);
                }
            }
        }

        static int FindSpacedOnes(string s)
        {
            // List of indexes of 1s in the string
            List<int> arr = BuildOnesArray(s);
            //if (s.Length < 3)
            //    return 0;

            //  List of indexes to odd indexes in arr
            List<int> odd = new List<int>(), even = new List<int>();

            //  evenIndex has indexes into arr to bracket even numbers
            //  oddIndex has indexes into arr to bracket odd numbers
            List<Pair<int>> evenIndex = new List<Pair<int>>(), 
                oddIndex = new List<Pair<int>>(); 
            BuildIndexes(arr, 
                ref even, ref odd, 
                ref evenIndex, ref oddIndex);

            int iterations = 0;
            for (int i = 1; i < arr.Count-1; i++)
            {
                int target = arr[i];
                bool found = FindCandidate(target, arr, odd, oddIndex[i], ref iterations) || 
                    FindCandidate(target, arr, even, evenIndex[i], ref iterations);
                if (found)
                    return iterations;
            }
            return iterations;
        }
        static IEnumerable<string> PowerSet(int n)
        {
            for (long i = (1L << (n-1)); i < (1L << n); i++)
            {
                yield return Convert.ToString(i, 2).PadLeft(n, '0');
            }
        }
        static void Main(string[] args)
        {
            for (int i = 5; i < 64; i++)
            {
                int c = 0;
                string hardest_string = "";
                foreach (string s in PowerSet(i))
                {
                    int cost = find_spaced_ones(s);
                    if (cost > c)
                    {
                        hardest_string = s;
                        c = cost;
                        Console.Write("{0} {1} {2}\r", i, c, hardest_string);
                    }
                }
                Console.WriteLine("{0} {1} {2}", i, c, hardest_string);
            }
        }
    }
}

Принципиальные различия:

1. Исчерпывающий поиск решений
   Этот код генерирует набор данных мощности, чтобы найти самый сложный вход для решения этого алгоритма.
2. Все решения по сравнению с самыми трудными для решения
   Код предыдущего вопроса сгенерировал все решения с использованием генератора Python. Этот код просто отображает самое сложное для каждой длины шаблона.
3. Алгоритм оценки
   Этот код проверяет расстояние от среднего элемента до его левого и правого края. Код Python проверял, была ли сумма выше или ниже 0.
4. сведения о кандидате
   Текущий код работает от середины к краю, чтобы найти кандидата. Код в предыдущей задаче работал от краев к середине. Это последнее изменение дает значительное улучшение производительности.
5. Использование четных и нечетных пулов
   Основываясь на наблюдениях в конце этой записи, код ищет пары четных чисел пар нечетных чисел, чтобы найти L и U, сохраняя M фиксированным. Это уменьшает количество поисков путем предварительного вычисления информации. Соответственно, код использует два уровня косвенности в основном цикле FindCandidate и требует двух вызовов FindCandidate для каждого среднего элемента: один раз для четных чисел и один раз для нечетных.

Общая идея - работать с индексами, а не с необработанным представлением данных. Вычисление массива, в котором появляются единицы, позволяет алгоритму работать во времени, пропорциональном количеству единиц в данных, а не во времени, пропорциональном длине данных. Это стандартное преобразование: создайте структуру данных, которая обеспечивает более быструю работу при сохранении эквивалентности задачи.

Результаты устарели: удалены.

---

Редактировать: 2009-10-16 18: 48

На данных yx, которым доверяют другие ответы как репрезентативные данные для вычисления, я получаю эти результаты ... Я удалил их. Они устарели.

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

---

Редактировать: 2009-10-17 13: 30

Дальнейшие наблюдения по этому вопросу.

Сначала преобразуйте строки из 0 и 1 в массив индексов для каждой позиции 1. Скажем, длина этого массива A равна X. Тогда цель состоит в том, чтобы найти

0 <= L < M < U <= X-1

такой, что

A[M] - A[L] = A[U] - A[M]

или

2*A[M] = A[L] + A[U]

Поскольку 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 :

M  L  U
0  0  0
   1  2
   2  1
1  0  2
   1  1
   2  0
2  0  1
   1  0
   2  2

На самом деле, вы можете объединить это с четным / нечетным наблюдением и разделить их на значения мод 6:

M  L  U
0  0  0
   1  5
   2  4
   3  3
   4  2
   5  1

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

Answer 6

Это может помочь ....

Эта проблема сводится к следующему:

Для заданной последовательности натуральных чисел найдите смежную подпоследовательность, разделенную на префикс и суффикс, такой, чтобы сумма префикса подпоследовательности была равна сумме суффикса подпоследовательности.

Например, для последовательности [ 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).

К сожалению, я не уверен, куда идти отсюда.

Answer 7

Еще не смог найти решение :(, но есть идеи.

Что если мы начнем с обратной задачи: построить последовательность с максимальным числом 1 с и БЕЗ любых равномерно распределенных трио. Если вы можете доказать, что максимальное число 1 равно o (n), то вы можете улучшить свою оценку, выполняя итерацию только по списку только 1.

Answer 8

Я подумал о подходе «разделяй и властвуй», который может сработать.

Во-первых, при предварительной обработке вам нужно вставить все числа, меньшие половины вашего размера ввода ( 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: возврат (0, {4,5,6,7}) 0101: возврат (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: возврат (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) как насколько я могу судить. Я вернусь к этому позже и попытаюсь уточнить последний шаг.

РЕДАКТИРОВАТЬ: изменил мой ответ, чтобы отразить комментарий Велбога. Извините за ошибку. Я также напишу немного псевдокода позже, когда у меня будет немного больше времени, чтобы расшифровать то, что я написал снова. ; -)

Answer 9

Забавный вопрос, но как только вы поймете, что фактический паттерн между двумя '1 не имеет значения, алгоритм становится:

• сканирование ищет '1'
• начиная со следующего сканирования позиции для другого '1' (до конца массива минус расстояние от текущего первого '1', иначе 3-й '1' будет вне границ)
• если в позиции 2-го '1' плюс расстояние до первого 1 'третьего' 1 'найдены равные пробелы.

В коде JTest fashion, (обратите внимание, этот код написан не для того, чтобы быть наиболее эффективным, и я добавил несколько println, чтобы посмотреть, что произойдет.)

import java.util.Random;

import junit.framework.TestCase;

public class AlgorithmTest extends TestCase {

 /**
  * Constructor for GetNumberTest.
  *
  * @param name The test's name.
  */
 public AlgorithmTest(String name) {
  super(name);
 }

 /**
  * @see TestCase#setUp()
  */
 protected void setUp() throws Exception {
  super.setUp();
 }

 /**
  * @see TestCase#tearDown()
  */
 protected void tearDown() throws Exception {
  super.tearDown();
 }

 /**
  * Tests the algorithm.
  */
 public void testEvenlySpacedOnes() {

  assertFalse(isEvenlySpaced(1));
  assertFalse(isEvenlySpaced(0x058003));
  assertTrue(isEvenlySpaced(0x07001));
  assertTrue(isEvenlySpaced(0x01007));
  assertTrue(isEvenlySpaced(0x101010));

  // some fun tests
  Random random = new Random();

  isEvenlySpaced(random.nextLong());
  isEvenlySpaced(random.nextLong());
  isEvenlySpaced(random.nextLong());
 }

 /**
  * @param testBits
  */
 private boolean isEvenlySpaced(long testBits) {
  String testString = Long.toBinaryString(testBits);
  char[] ones = testString.toCharArray();
  final char ONE = '1';

  for (int n = 0; n < ones.length - 1; n++) {

   if (ONE == ones[n]) {
    for (int m = n + 1; m < ones.length - m + n; m++) {

     if (ONE == ones[m] && ONE == ones[m + m - n]) {
      System.out.println(" IS evenly spaced: " + testBits + '=' + testString);
      System.out.println("               at: " + n + ", " + m + ", " + (m + m - n));
      return true;
     }
    }
   }
  }

  System.out.println("NOT evenly spaced: " + testBits + '=' + testString);
  return false;
 }
}

Answer 10

Для простого типа задачи (т. Е. Вы ищете три «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 такие тройки). Конечно, вы ищете только один из них, но я пока не знаю, как его найти ...