2014 dxdy logo

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

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




 
 Оптимизировать алгоритм
Сообщение18.11.2010, 14:09 
Возможно я туплю, но что-то не могу ничего придумать.
Дано $n$ точек с номерами от 1 до $n$. Каждой точке поставлено в соответствие еще 2 точки - предыдущая и следующая, так что все множество точек разбивается на множество циклов произвольной длины (гарантируется, что длина цикла не меньше 3-х точек). Надо найти алгоритм последовательного вывода циклов с последовательным выводом точек в каждом цикле.
Сейчас у меня алгоритм $O(n^2)$. Можно ли сделать быстрее? Скорость $O(n \ln n)$ вполне бы меня удовлетворила.
Пытался делать по аналогии с сортировкой массива, но не получается.

 
 
 
 Re: Оптимизировать алгоритм
Сообщение18.11.2010, 14:35 
Дык, простой обход массива, с запоминанием встреченных точек - $O(n)$ плюс $O(n)$ памяти.

 
 
 
 Re: Оптимизировать алгоритм
Сообщение18.11.2010, 14:42 
О! Действительно! Спасибо! :-)

-- Чт ноя 18, 2010 15:56:57 --

Нет, не понял.
Я Вас понял так: для данного массива создаем новый двумерный массив, в каждый столбец которого пишутся точки своего цикла Рассматриваем текущую точку. Пробегаемся по столбцам нового массива по концам уже найденных цепочек. Если на каком-то шаге точка подходит к началу/концу данной цепочки - дописываем ее в начало/конец этой цепочки. Если ни на каком шаге точка не подошла, то заводим новый столбец в двумерном массиве.
Но тогда получается, что мы на самом деле не можем различить точку нового цикла и далекую точку старого цикла.
Например, если дано $n$ вершин и они организованы в цикл $1-2-...-n-1$, а в исходном массиве записаны как $1,3,5,...2,4,6,...$, то мы так в конце построим не одну итоговую цепочку, а несколько.

Что я не понял?

 
 
 
 Re: Оптимизировать алгоритм
Сообщение18.11.2010, 15:27 
Аватара пользователя
В ящиках с номерами от $1$ до $n$ лежат числа. Берём число из первого непустого ящика и записываем его, за ним следующее и т.д. (до окончания цикла). Снова берём число из первого непустого ящика и т.д. С самого начала храним (и обновляем) номер первого непустого ящика, последнего непустого ящика, следующего непустого ящика (это для каждого непустого ящика).

 
 
 
 Re: Оптимизировать алгоритм
Сообщение18.11.2010, 15:35 
TOTAL писал(а):
В ящиках с номерами от $1$ до $n$ лежат числа. Берём число из первого непустого ящика и записываем его, за ним следующее и т.д. (до окончания цикла). Снова берём число из первого непустого ящика и т.д. С самого начала храним (и обновляем) номер первого непустого ящика, последнего непустого ящика, следующего непустого ящика (это для каждого непустого ящика).

Ага! :-) Если я правильно Вас понял, то у меня так и работает. Но это как раз в худшем случае $O(n^2)$. Т.е. если эти $n$ точек организованы в, скажем, $\frac{n}{5}$ циклов длиной 5, причем точки каждого цикла равномерно распределены по данному массиву, то нам будет необходимо пройти по $n$ точек, чтобы вытащить каждый цикл, т.е. всего $O(n \cdot \frac{n}{5})=O(n^2)$ (ну там даже если пустые элементы игнорировать все равно получится $O(n^2)$).
Правильно я понял?

-- Чт ноя 18, 2010 16:37:18 --

venco, TOTAL М.б. я какой-то момент упустил? (Скажите, проект и так горит...)

-- Чт ноя 18, 2010 16:51:39 --

Может быть так сделать: рассматриваем входящие точки как куски циклов длины 1, для которых известны точки, которые можно подсоединить к их концам. Создаем новый пустой массив кусков циклов. Проходим по старому массиву, для каждого куска цикла старого массива пробегаемся по новому массиву и проверяем - подходит этот кусок хотя бы к одному куску из нового массива, если подходит - то соединяем куски, иначе - пишем его в новый столбец нового массива. После прохода по старому массиву новый массив будет представлять из себя тоже массив кусков циклов, только кусков будет меньше и они будут длиннее. Записываем теперь новый массив в старый, а новый очищаем и повторяем итерации до тех пор пока не образуются полные циклы. И получается еще, что если на каком-то шаге образовался полный цикл, то его можно вывести и не рассматривать...
М.б. так будет быстрее работать :roll: ? Правда писанины будет много и геморроя тоже...

 
 
 
 Re: Оптимизировать алгоритм
Сообщение18.11.2010, 15:56 
Аватара пользователя
Sonic86 в сообщении #376971 писал(а):
то нам будет необходимо пройти по $n$ точек, чтобы вытащить каждый цикл
Не по всем, т.к. номер следующегоо ящика из цикла известен.

 
 
 
 Re: Оптимизировать алгоритм
Сообщение18.11.2010, 17:32 
Sonic86, пробегаете цикл один раз. Встретив новую точку, от неё пробегаете внутренний цикл, помечая всё на ходу. Каждая точка встретится максимум 2 раза, один раз во внешнем цикле, и максимум один раз во внутреннем.

 
 
 
 Re: Оптимизировать алгоритм
Сообщение18.11.2010, 20:24 
Аватара пользователя
0. Вспомогательная память - битовый вектор соответственно числу точек, начальное значение 0.
1. Внешний цикл. Находим нулевой элемент вектора. Печатаем "начало нового цикла". Передаём номер найденного элемента во внутренний цикл. Если все элементы ненулевые - конец работы.
2. Внутренний цикл. Начинаем с переданного элемента. Выводим его.
Переходим к следующему. Если он помечен 1, то заканчиваем внутренний цикл. Иначе помечаем его 1 и выводим номер.

 
 
 
 Re: Оптимизировать алгоритм
Сообщение18.11.2010, 21:29 
Евгений Машеров в сообщении #377083 писал(а):
0. Вспомогательная память - битовый вектор соответственно числу точек, начальное значение 0.
Ну именно битовый вектор необязателен. Если элементы нетривиальной структуры, вообще лучше будет хеш-таблица. А можно и на самих элементах флаги ставить, если есть такая возможность — самый быстрый доступ. :-)

 
 
 
 Re: Оптимизировать алгоритм
Сообщение19.11.2010, 06:35 
venco, TOTAL
Прошу прощенья, я затупил, я слишком упростил задачу, у меня-то тут вершины пронумерованы не $1,2,...,n$, а $m_1,m_2,...m_n$ и поэтому когда номера $1,2,...,n$, то Вы можете говорить, что
TOTAL писал(а):
Не по всем, т.к. номер следующегоо ящика из цикла известен.

venco писал(а):
Встретив новую точку, от неё пробегаете внутренний цикл, помечая всё на ходу.

а я говорил, что ищу за $O(n)$. Ну я теперь номера $m_1,m_2,...m_n$ отсортировал и ищу за $O(\ln n)$, так что теперь все работает быстро.
Спасибо большое! :-)

 
 
 [ Сообщений: 10 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group