Комментарии 13
Хорошая статья, примеров кода побольше бы.
+1
Где учитесь, если не секрет?
+1
>Итого, имеем алгоритм сортировки по месту, работающий за время O(n^0.5) в худшем случае.
Если это не опечатка — асимптотическая сложность сортировки за корень, то можно как-то это пояснить?
Вроде бы мы проходим по циклу длины n и каждая итерация имеет сложность корень => O(n^1.5)
что-то упускаю?
Если это не опечатка — асимптотическая сложность сортировки за корень, то можно как-то это пояснить?
Вроде бы мы проходим по циклу длины n и каждая итерация имеет сложность корень => O(n^1.5)
что-то упускаю?
+2
Большое спасибо за статью!
Особенно интересно было почитать про оценку скорости работы и сравнение с другими алгоритмами.
Особенно интересно было почитать про оценку скорости работы и сравнение с другими алгоритмами.
+1
Большое спасибо за статью!
Особенно интересно было почитать про оценку скорости работы и сравнение с другими алгоритмами.
Особенно интересно было почитать про оценку скорости работы и сравнение с другими алгоритмами.
0
Спасибо! Надо будет запомнить, потому что сколько мне не рассказывали про разные структуры, эту как-то упустили из виду. :) Радует, что идея запоминается (а если что-то не запомнилось — додумывается) на ходу, при этом в ней я не заметил «подводных камней», как, например, часто бывает при реализации всяких деревьев отрезков и т.п.
+1
Я могу конечно ошибаться, но не будет ли время сортировки занимать чуть больше времени (не O(n^1.5), а O(n^2)), ведь сначала n элементов из X надо записать/вставить в таблицу, а потом столько же оттуда исключить, т.е. n*(n^0.5)*(n^0.5)?
Заранее спасибо, если разъясните мои ошибки (в случае, если все же ошибаюсь).
Заранее спасибо, если разъясните мои ошибки (в случае, если все же ошибаюсь).
0
На вставку одного элемента тратится не более 2n1/2 действий. На вставку n элементов — не более 2n3/2 действий. После того, как таблица построена, из нее извлекаются по очереди все элементы, на извлечение одного элемента тратим не более 2n1/2 шагов, на извлечение всех элементов — 2n3/2 шагов. Т.к. эти два процесса (создание таблицы и ее уничтожение) происходят последовательно, то общая сложность не превышает суммы сложностей отдельных шагов, т.е. 4n3/2 или O(n3/2)…
+2
А почему сказано, что в пирамиде искать нужно полным перебором? Двоичный поиск же за log(n)… Или я что-то упускаю?
0
Хм, насколько я понимаю, определяющее свойство пирамиды — ключ любого узла не меньше любого ключа в соответствующем поддереве (с корнем в данном узле). Если я хочу найти некоторый элемент в пирамиде, то я начинаю с корня (точка доступа к пирамиде). Если искомый элемент больше ключа в корне, то сразу ясно, что такого ключа в пирамиде нет, ибо корень хранит наибольший ключ. Если ключи совпадают, то мы нашли то, что искали, правда, если цель — найти все такие ключи, то придется поиск продолжить. И тут мы плавно переходим к третьей альтернативе — искомый ключ меньше корневого. Значит его надо искать либо в правом поддереве, либо в левом. Но в каком конкретно? А этого то мы и не знаем — значит придется искать и там, и там. Т.е. никакого разделения задачи на две подзадачи с последующим отбрасыванием одной из них (двоичный поиск) не получается. Получается, что сравнением заданного ключа с корнем мы добились только отбрасывания одного единственного ключа из всего дерева — поэтому-то в худшем случае поиск и будет требовать O(n) действий. Как-то так…
0
Кстати, ресайз в два раза как в сторону увеличения, так и уменьшения, можно сделать за O(n) вместо полного перестроения таблицы. Соответственно, сливая по две соседние строки, или записывая элементы каждой строки поочерёдно в две соседние.
0
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Таблицы Юнга в задачах поиска и сортировки