2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Сложность одного алгоритма
Сообщение27.06.2021, 15:11 


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

Пусть $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)$.

 Профиль  
                  
 
 Re: Сложность одного алгоритма
Сообщение27.06.2021, 15:28 
Заслуженный участник
Аватара пользователя


16/07/14
8349
Цюрих
gogoshik в сообщении #1524505 писал(а):
замена двух символов, встречающихся в строке в виде $(\dots xy \dots yx \dots)$, на один
Имеется в виду - на один произвольный?
gogoshik в сообщении #1524505 писал(а):
существует квадратичный алгоритм проверки сокращения строки с помощью операций $\alpha, \beta$ до одной из строк -- пустая строка, $(xyxy)$, $(xyzxyz)$
А разве начав со строки $abcdabcd$ можно получить какую-то другую?
gogoshik в сообщении #1524505 писал(а):
Удаление элемента связного списка имеет сложность $O(1)$.
Удаление элемента по индексу занимает линейное время (нужно еще найти элемент). Так что тут что-то более хитрое нужно.

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

 Профиль  
                  
 
 Re: Сложность одного алгоритма
Сообщение27.06.2021, 15:52 


11/12/16
403
сБп
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$, то есть что "сокращения не существует". Потребуется модифицировать алгоритм, добавить повторение операций, так как по идее должна получиться пустая строка с результатом на выходе "сокращение существует". Но это вроде не увеличит сложность.

 Профиль  
                  
 
 Re: Сложность одного алгоритма
Сообщение27.06.2021, 16:06 
Заслуженный участник
Аватара пользователя


16/07/14
8349
Цюрих
gogoshik в сообщении #1524514 писал(а):
Речь же идет об алгоритме проверки
А, я думал, что утверждается, что любая строка сокращается, и нужно найти последовательность сокращений.
gogoshik в сообщении #1524514 писал(а):
Но это вроде не увеличит сложность
Это нужно доказывать. Потенциально вы на шаге 4-5 можете удалить всего одну пару символов, и его придется повторить линейное число раз, что сделает общее время кубическим.

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

 Профиль  
                  
 
 Re: Сложность одного алгоритма
Сообщение27.06.2021, 16:13 


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

 Профиль  
                  
 
 Re: Сложность одного алгоритма
Сообщение27.06.2021, 16:22 
Заслуженный участник
Аватара пользователя


16/07/14
8349
Цюрих
gogoshik в сообщении #1524520 писал(а):
Почему вы так подумали? Вам формулировка не нравится?
Да, потому что не очень понятно, что такое "проверка сокращения". Если читать буквально - то получается, что дано сокращение, и надо его проверить. ИМХО лучше сказать "проверки возможности сокращения".

 Профиль  
                  
 
 Re: Сложность одного алгоритма
Сообщение27.06.2021, 16:42 


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

-- 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)$.

 Профиль  
                  
 
 Re: Сложность одного алгоритма
Сообщение27.06.2021, 18:12 


27/08/16
9426
gogoshik в сообщении #1524505 писал(а):
Пусть $s$ -- конечная строка символов произвольного алфавита, в которой каждый символ содержится ровно два раза.
Что такое $n$?
Алфавит функция $n$?

-- 27.06.2021, 18:36 --

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

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

 Профиль  
                  
 
 Re: Сложность одного алгоритма
Сообщение27.06.2021, 19:07 


11/12/16
403
сБп
realeugene в сообщении #1524553 писал(а):
Что такое $n$?
Почитайте. У меня написано.
realeugene в сообщении #1524553 писал(а):
почему не сделать это за линейное время?
Ну, допустим, у вас получится проверить и выполнить удаление двух одинаковых символов идущих друг за другом за некоторое число проходов. А как вы без двойных циклов, итераций выполните проверку и замену двух символов, встречающихся в строке, на один?

 Профиль  
                  
 
 Re: Сложность одного алгоритма
Сообщение27.06.2021, 19:24 


27/08/16
9426
gogoshik в сообщении #1524558 писал(а):
Почитайте. У меня написано.
Я и прочитал. Алфавитом обычно называют фиксированное в задаче константное множество. А у вас нечто иное.

gogoshik в сообщении #1524558 писал(а):
А как вы без двойных циклов, итераций выполните проверку и замену двух символов, встречающихся в строке, на один?
Тривиально, построив простейшие структуры данных, позволяющие выполнить каждую такую операцию за $O(1)$.

 Профиль  
                  
 
 Re: Сложность одного алгоритма
Сообщение27.06.2021, 21:34 
Заслуженный участник
Аватара пользователя


16/07/14
8349
Цюрих
gogoshik в сообщении #1524534 писал(а):
Вы про такое?
Примерно. Только нам еще пункты 2-3 (удаление элемента, встречающегося два раза подряд) повторить придется.
gogoshik в сообщении #1524534 писал(а):
Что-то стало думаться, что тут ничего хитрее, то есть в целом оптимальнее $O(n^3)$ не придумать
Придумать, конечно. Только сначала подумайте - зависит ли возможность сокращения от порядка операций, или нет? Т.е. может ли оказаться так, что строку сократить можно, мы применили к ней одну из операций, и новую строку сократить уже нельзя?

 Профиль  
                  
 
 Re: Сложность одного алгоритма
Сообщение27.06.2021, 22:03 


11/12/16
403
сБп
mihaild в сообщении #1524577 писал(а):
Придумать, конечно.
То есть и вы думаете, что существует линейный алгоритм?

 Профиль  
                  
 
 Re: Сложность одного алгоритма
Сообщение27.06.2021, 22:11 


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

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

 Профиль  
                  
 
 Re: Сложность одного алгоритма
Сообщение28.06.2021, 20:09 


12/07/15
2907
г. Чехов
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).

 Профиль  
                  
 
 Re: Сложность одного алгоритма
Сообщение28.06.2021, 20:51 
Заслуженный участник
Аватара пользователя


16/07/14
8349
Цюрих
Что этот вариант алгоритма выдаст на строке $abcdacbd$?

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 24 ]  На страницу 1, 2  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group