nickme Jun 14 2011 at 17:07

Таблицы Юнга в задачах поиска и сортировки

6 min

7.1K

Algorithms*

From sandbox

+50

Comments 13

ninacarrot Jun 14 2011 at 19:04

Хорошая статья, примеров кода побольше бы.

Andrew1000000 Jun 14 2011 at 19:51

Где учитесь, если не секрет?

varagian Jun 14 2011 at 20:35

>Итого, имеем алгоритм сортировки по месту, работающий за время O(n^0.5) в худшем случае.

Если это не опечатка — асимптотическая сложность сортировки за корень, то можно как-то это пояснить?

Вроде бы мы проходим по циклу длины n и каждая итерация имеет сложность корень => O(n^1.5)

что-то упускаю?

nickme Jun 14 2011 at 20:37

Уже исправил, спасибо!

Yaraife Jun 14 2011 at 20:52

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

Yaraife Jun 14 2011 at 21:48

WingedFlame Jun 14 2011 at 23:05

Спасибо! Надо будет запомнить, потому что сколько мне не рассказывали про разные структуры, эту как-то упустили из виду. :) Радует, что идея запоминается (а если что-то не запомнилось — додумывается) на ходу, при этом в ней я не заметил «подводных камней», как, например, часто бывает при реализации всяких деревьев отрезков и т.п.

Zordhauer Jun 17 2011 at 08:07

Я могу конечно ошибаться, но не будет ли время сортировки занимать чуть больше времени (не O(n^1.5), а O(n^2)), ведь сначала n элементов из X надо записать/вставить в таблицу, а потом столько же оттуда исключить, т.е. n*(n^0.5)*(n^0.5)?
Заранее спасибо, если разъясните мои ошибки (в случае, если все же ошибаюсь).

nickme Jun 17 2011 at 08:15

На вставку одного элемента тратится не более 2n^1/2 действий. На вставку n элементов — не более 2n^3/2 действий. После того, как таблица построена, из нее извлекаются по очереди все элементы, на извлечение одного элемента тратим не более 2n^1/2 шагов, на извлечение всех элементов — 2n^3/2 шагов. Т.к. эти два процесса (создание таблицы и ее уничтожение) происходят последовательно, то общая сложность не превышает суммы сложностей отдельных шагов, т.е. 4n^3/2 или O(n^3/2)…

Zordhauer Jun 17 2011 at 08:47

Благодарю. Теперь осознал свою глупость =)

mikhanoid Jun 17 2011 at 08:47

А почему сказано, что в пирамиде искать нужно полным перебором? Двоичный поиск же за log(n)… Или я что-то упускаю?

nickme Jun 17 2011 at 12:43

Хм, насколько я понимаю, определяющее свойство пирамиды — ключ любого узла не меньше любого ключа в соответствующем поддереве (с корнем в данном узле). Если я хочу найти некоторый элемент в пирамиде, то я начинаю с корня (точка доступа к пирамиде). Если искомый элемент больше ключа в корне, то сразу ясно, что такого ключа в пирамиде нет, ибо корень хранит наибольший ключ. Если ключи совпадают, то мы нашли то, что искали, правда, если цель — найти все такие ключи, то придется поиск продолжить. И тут мы плавно переходим к третьей альтернативе — искомый ключ меньше корневого. Значит его надо искать либо в правом поддереве, либо в левом. Но в каком конкретно? А этого то мы и не знаем — значит придется искать и там, и там. Т.е. никакого разделения задачи на две подзадачи с последующим отбрасыванием одной из них (двоичный поиск) не получается. Получается, что сравнением заданного ключа с корнем мы добились только отбрасывания одного единственного ключа из всего дерева — поэтому-то в худшем случае поиск и будет требовать O(n) действий. Как-то так…

SergeyBankevich Jul 3 2011 at 22:34

Кстати, ресайз в два раза как в сторону увеличения, так и уменьшения, можно сделать за O(n) вместо полного перестроения таблицы. Соответственно, сливая по две соседние строки, или записывая элементы каждой строки поочерёдно в две соседние.

Show the best of all time