Сложность одного алгоритма

[gogoshik]

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

Пусть $s$ -- конечная строка символов произвольного алфавита, в которой каждый символ содержится ровно два раза. Допускается выполнение следующих операций: $(\alpha)$ -- удаление двух одинаковых символов идущих друг за другом, то есть символов вида $(xx)$; $(\beta)$ -- замена двух символов, встречающихся в строке в виде $(\dots xy \dots yx \dots)$, на один.

Утверждается, что: существует квадратичный алгоритм проверки сокращения строки с помощью операций $\alpha, \beta$ до одной из строк -- пустая строка, $(xyxy)$, $(xyzxyz)$.

Пусть на входе содержится строка $s$ длины $n$. В дальнейшем вся нумерация списков и массивов будет начинаться с единицы.
1) Представим $s$ в виде соответствующего связного списка, который назовем $L$. Для этого потребуется один проход по $s$, то есть $n$ шагов. В этом же проходе создадим массив всех элементов строки, который обозначим через $W$. Общая сложность $O(n)$.
2) Будем выполнять проход по $W$, начиная со второго элемента. На каждом шаге будем проверять равенство текущего и предыдущего элементов. Если равенство выполняется, то будем записывать индексы этих элементов в новый массив $A$. Общая сложность $O(n)$.
3) Будем выполнять проход по $A$. На каждом шаге будем удалять элемент $L$ соответсвующего индекса. Удаление элемента связного списка имеет сложность $O(1)$. Поэтому общая сложность прохода $O(n)$.
4) Будем выполнять проход по $L$, начиная с элемента под номером $i = 2$. Запомним элементы $i$ и $(i - 1)$. На следущих шагах сравним текущий и предыдущие элементы с элементами памяти согласно условию (a): текущий элемент равен первому элементу памяти и предыдущий элемент равен второму элементу памяти. Если условие выполняется, то удалим второй элемент $L$ и предыдущий элемент текущего шага. Повторим проход. Сложность каждого прохода $O(n)$.
5) Если условие (a) не выполняется, то выполним итерацию прохода (4), начиная с $i = i + 1$. Повторим (4) и (5) пункты $(n/2)$ раз. Каждый повторение сложностью $O(n)$. Общая сложность $O(n^2)$.

[mihaild]

gogoshik в сообщении #1524505 писал(а):

замена двух символов, встречающихся в строке в виде $(\dots xy \dots yx \dots)$, на один

Имеется в виду - на один произвольный?

gogoshik в сообщении #1524505 писал(а):

существует квадратичный алгоритм проверки сокращения строки с помощью операций $\alpha, \beta$ до одной из строк -- пустая строка, $(xyxy)$, $(xyzxyz)$

А разве начав со строки $abcdabcd$ можно получить какую-то другую?

gogoshik в сообщении #1524505 писал(а):

Удаление элемента связного списка имеет сложность $O(1)$.

Удаление элемента по индексу занимает линейное время (нужно еще найти элемент). Так что тут что-то более хитрое нужно.

Что ваш алгоритм выдаст на строке $zxyyxz$?

[gogoshik]

mihaild в сообщении #1524509 писал(а):

Имеется в виду - на один произвольный?

Да. Я имел ввиду, что последовательность символов $(\dots xy \dots yx \dots)$ может быть сокращена либо до $(\dots x \dots x \dots)$, либо $(\dots y \dots y \dots)$.

mihaild в сообщении #1524509 писал(а):

начав со строки $abcdabcd$ можно получить какую-то другую?

Нельзя. Тогда алгоритм выдаст, что сокращения данной строки не существует. Речь же идет об алгоритме проверки
сокращается ли какая-то строка или нет. В конец надо добавить проверку $L$ на равенство одному из: пустая строка, пустая строка, $(xyxy)$, $(xyzxyz)$. Это не изменит сложность.

mihaild в сообщении #1524509 писал(а):

Что ваш алгоритм выдаст на строке $zxyyxz$?

Я понимаю вас. Выдаст $zz$, то есть что "сокращения не существует". Потребуется модифицировать алгоритм, добавить повторение операций, так как по идее должна получиться пустая строка с результатом на выходе "сокращение существует". Но это вроде не увеличит сложность.

[mihaild]

gogoshik в сообщении #1524514 писал(а):

Речь же идет об алгоритме проверки

А, я думал, что утверждается, что любая строка сокращается, и нужно найти последовательность сокращений.

gogoshik в сообщении #1524514 писал(а):

Но это вроде не увеличит сложность

Это нужно доказывать. Потенциально вы на шаге 4-5 можете удалить всего одну пару символов, и его придется повторить линейное число раз, что сделает общее время кубическим.

Еще нужно доказать, что, если ваш алгоритм не нашел последовательности операций, то её вообще не существует - вдруг ваш алгоритм зашел в тупик, а можно было, проведя операции в другом порядке, удалить всё?

[gogoshik]

mihaild в сообщении #1524517 писал(а):

А, я думал, что утверждается, что любая строка сокращается, и нужно найти последовательность сокращений

Вы так поняли или прочитали? Вот у меня написано, что: существует квадратичный алгоритм проверки сокращения строки с помощью операций $\alpha, \beta$ до одной из строк -- пустая строка, $(xyxy)$, $(xyzxyz)$. Это означает, что алгоритм проверки (слово "проверки" можно заменить на "распознавания") любой строки, а не алгоритм сокращения. Почему вы так подумали? Вам формулировка не нравится?

[mihaild]

gogoshik в сообщении #1524520 писал(а):

Почему вы так подумали? Вам формулировка не нравится?

Да, потому что не очень понятно, что такое "проверка сокращения". Если читать буквально - то получается, что дано сокращение, и надо его проверить. ИМХО лучше сказать "проверки возможности сокращения".

[gogoshik]

Может быть. Спасибо. Хотя, если понимать вас буквально. То дано некоторое сокращение из вышеуказанного списка и дана строка. И мы хотим просто проверить, сокращается ли (либо да, либо нет) она до данного сокращения.

-- 27.06.2021, 17:05 --

mihaild в сообщении #1524517 писал(а):

Потенциально вы на шаге 4-5 можете удалить всего одну пару символов, и его придется повторить линейное число раз, что сделает общее время кубическим.

Не могли бы объяснить это место? Вы про такое?

4) Будем выполнять проход по $L$, начиная с элемента под номером $i = 2$. Запомним элементы $i$ и $(i - 1)$. На следущих шагах сравним текущий и предыдущие элементы с элементами памяти согласно условию (a): текущий элемент равен первому элементу памяти и предыдущий элемент равен второму элементу памяти. Если условие выполняется, то удалим второй элемент $L$ и предыдущий элемент текущего шага. Повторим проход. Сложность одного прохода $O(n)$.
5) Если условие (a) не выполняется, то выполним итерацию прохода (4) сложностью $O(n)$, начиная с $i = i + 1$.
6) Повторим (4) и (5) пункты $(n/2)$ раз. То есть, пункт (4) -- $O(n)$, пункт (5) -- $O(n)$ и повторение $O(n/2)$ . В итоге общая сложность будет $O(n^3)$.

-- 27.06.2021, 17:31 --

Что-то стало думаться, что тут ничего хитрее, то есть в целом оптимальнее $O(n^3)$ не придумать. Тупиковый путь. Изначально была задумка придумать алгоритм $O(n \log n)$.

[realeugene]

gogoshik в сообщении #1524505 писал(а):

Пусть $s$ -- конечная строка символов произвольного алфавита, в которой каждый символ содержится ровно два раза.

Что такое $n$?
Алфавит функция $n$?

-- 27.06.2021, 18:36 --

gogoshik в сообщении #1524505 писал(а):

Утверждается, что: существует квадратичный алгоритм проверки сокращения строки с помощью операций $\alpha, \beta$ до одной из строк -- пустая строка, $(xyxy)$, $(xyzxyz)$.

Непонятно, почему не сделать это за линейное время?

[gogoshik]

realeugene в сообщении #1524553 писал(а):

Что такое $n$?

Почитайте. У меня написано.

realeugene в сообщении #1524553 писал(а):

почему не сделать это за линейное время?

Ну, допустим, у вас получится проверить и выполнить удаление двух одинаковых символов идущих друг за другом за некоторое число проходов. А как вы без двойных циклов, итераций выполните проверку и замену двух символов, встречающихся в строке, на один?

[realeugene]

gogoshik в сообщении #1524558 писал(а):

Почитайте. У меня написано.

Я и прочитал. Алфавитом обычно называют фиксированное в задаче константное множество. А у вас нечто иное.

gogoshik в сообщении #1524558 писал(а):

А как вы без двойных циклов, итераций выполните проверку и замену двух символов, встречающихся в строке, на один?

Тривиально, построив простейшие структуры данных, позволяющие выполнить каждую такую операцию за $O(1)$.

[mihaild]

gogoshik в сообщении #1524534 писал(а):

Вы про такое?

Примерно. Только нам еще пункты 2-3 (удаление элемента, встречающегося два раза подряд) повторить придется.

gogoshik в сообщении #1524534 писал(а):

Что-то стало думаться, что тут ничего хитрее, то есть в целом оптимальнее $O(n^3)$ не придумать

Придумать, конечно. Только сначала подумайте - зависит ли возможность сокращения от порядка операций, или нет? Т.е. может ли оказаться так, что строку сократить можно, мы применили к ней одну из операций, и новую строку сократить уже нельзя?

[gogoshik]

mihaild в сообщении #1524577 писал(а):

Придумать, конечно.

То есть и вы думаете, что существует линейный алгоритм?

[realeugene]

Однопроходный, да. Дрказательство его корректности - это самое сложное и интересное, конечно.

Откуда задача? Это тестовая задача какого-то собеседования при приеме на работу?

[Mihaylo]

1. Пробегаемся по алфавиту:
2. Берем пару символов и отыскиваем их в строке.
3. Возможны три случая:
3а. Порядок независимый xxyy.
3б. Порядок вложенный xyyx.
3в. Порядок спутанный xyxy.

Для спутанного порядка $\alpha$-операции и $\beta$-операции неприменимы, единственный выход - $\beta$-операции над x или y в "любовном треугольнике" с некоторым третьим символом z.
Возможные варианты:
1. Порядок xyzxzy, который может сводиться к xyxy с помощью $\beta$-операции.
2. Порядок нераспутываемый xyzxyz. Важно проверить, что нет порядка xyzwxyzw (более глубокие спутывания искать не требуется).

Итого алгоритм выдает единицу, если:
1. Либо вы не находите ни одной спутанной пары символов xyxy.
2. Либо у вас одна пара или одна тройка спутанных символов, но нет четверки спутанных символов.
Выдает нуль, если:
1. Спутано несколько пар или троек символов.
2. Либо хотя бы одна четверка спутанных символов.

Требуется доказать, что существует алгоритм O(n*n), а не O(n*n*n*n) - поиск четверок в лоб.

-- 28.06.2021, 22:25 --

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

Тогда алгоритм сводится к поиску всех спутанных двоек. Алгоритм выдает единицу, если:
1. Нет спутанных двоек.
2. Ровно одна спутанная двойка.
3. Ровно три спутанные двойки, состоящие из трех символов.
Иначе алгоритм выдает нуль.

Сложность O(n*n).

[mihaild]

Что этот вариант алгоритма выдаст на строке $abcdacbd$?