2014 dxdy logo

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

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




 
 Поиск в массиве
Сообщение03.10.2006, 19:36 
Здравствуйте!
Я пытаюсь придумать алгоритм для такой задачи. В неупорядоченном массиве размера n надо найти номера m-1 элементов таких, что в упорядоченном массиве данные элементы делят его на n/m упорядоченных массивов размером m.
Пробовала решать сортировкой, а затем выдавать номера in/m, i=1..m-1, но хочется, чтобы алгоритм работал, не выполняя самой сортировки, то есть за меньшее число шагов.
Посоветуйте, пожалуйста,что-нибудь.

 
 
 
 
Сообщение03.10.2006, 19:42 
Можна как-то попробовать сделать, чтобы эти куски размером m были неупорядочены. Но, мне кажется, что с сортировкой задача решается проще всего, то есть решение оптимально для понимания, но, возможно, не оптимально по времени выполнения.

 
 
 
 
Сообщение03.10.2006, 20:35 
Аватара пользователя
:evil:
Если по каким то причинам эффективность очень важна (а иначе, и впрямь, лучше сортировать), воспользуйтесь известной задачей о «голандском флаге». Она является поворяющимся шагом быстрой сортировки (qsort, quicksort). Для любого значения $x$ за один проход сегмента массива его можно реорганизовать на зоны $ < x$, $=x$ и $>x$.

Идея проста: выбираем произвольное значение. Делим массив на три зоны. Каждый из наших индексов $ \frac{i\,n}{m}$ попадает в одну из зон. Те, что попали в среднюю — найдены. Если в зоне нет ни одного индекса — забываем про нее. Иначе применяем к ней (и к попадающем в нее индексам) этот же процесс.

В среднем этот алгоритм дает линейное время, но при неудаче — квадратичное. На практике неудачи можно регулировать управляя выбором $x$. Кроме того, маленькие сегменты (меньше 10-15) может быть выгоднее отсортировать полностью каким нибудь пузырьком. Это уж надо на конкретной реализации выяснять.

 
 
 
 
Сообщение04.10.2006, 01:42 
Спасибо, что рассмотрели мою проблему. Мне вообще кажется, что если руководствоваться чем-то типа qsort, то можно даже в худшем случае получить сложность меньше квадратичной.

 
 
 
 
Сообщение04.10.2006, 02:17 
Аватара пользователя
:evil:
Вы не можете гарантировать, что не будете откусывать по два элемента на каждом проходе (то есть, получать две зоны по одному элементу). Отсюда и проблемы.

 
 
 
 
Сообщение04.10.2006, 17:41 
Еще придумал такое решение: разбиваем весь массив на эти отрезки, а потом в каждом отрезке если есть элемент меньший за левый и/или больший за правый, то меняем его местами с соответствующим. И так до тех пор, пока ничего менять не приходится. Только кажется сложность будет не меньше квадратической (правда и не больше, потому что за квадратическое время массив сортируется). Вообще кажется, что получить сложность лучше n log n (не знаю точно, но в худшем случае не придется ли массив в любом случае сортировать?) не выйдет.

 
 
 
 
Сообщение04.10.2006, 18:12 
Аватара пользователя
Если данные берутся не из головы, а поступают из какой-либо реальной системы, то, возможно, они могут быть более-менее хорошо описаны некоторым распределением (надо проанализировать данные). Тогда можно взять в качестве границ областей соответствующие квантили, что может дать распределение по группам, близкое к равномерному.

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


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