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