В этой статье в Википедии http://en.wikipedia.org/wiki/Quicksort#In-place_version предлагается, что O (logn) - это временная сложность пространства для сортировки по месту и http://futur3googl3r.blogspot.com/2008/08/google-interview-questions.html, этот сайт интервью предполагает, что это O (n) , Я думаю, что ответ O (n), но хотел знать, прав ли я.на месте быстрая сортировка имеет сложность пространства O (n) или O (logn)
В обеих статьях, сложность пространства, что они имеют в виду имеет дополнительного пространства (не считая места, необходимого для хранения исходного массива). Это дополнительно пространство может быть получено из стека вызовов, в дополнение к обычному случаю, когда объявлен дополнительный массив. Каждый рекурсивный вызов создает фрейм стека в стеке вызовов, который занимает пробел, а количество кадров стека зависит от размера ввода n, поэтому его нужно учитывать.
Давайте использовать статью в Википедии для справки, так как блог совершенно несовместим, как указал @Jim Mischel.
Для на месте быстрой сортировки, модификации от наивной реализации даст O(log n)дополнительное пространствов среднем вместо O(n)дополнительного пространства (во всех случаях) в наивной реализации. худшем случае сложность дополнительного пространства, как было указано правильно блога , является O(n), когда алгоритм встречает свой худший случай (отсортированный список, будет n рекурсивных вызовов, так что стек вызовов будет принимать up O(n)дополнительные пространство).
: (Спасибо @rici за указание) Тем не менее, блоггер только правильно, если мы предполагаем реализацию без оптимизации, как упоминалось в Wikipedia article. Можно улучшить алгоритм использования O(log n)дополнительно пространство в худшем случае, сначала рекурсивное на меньшем участке и выполнение хвостового вызова для более длинной части. Поскольку меньшая часть всегда меньше половины входного размера, будет не более O(log n) рекурсивных вызовов. Предполагая оптимизацию хвостового вызова, более длинная часть будет повторно использовать текущий стек стека без дополнительных пробелов. Если оптимизация хвостового вызова не выполняется, мы всегда можем написать итеративную реализацию с явным стеком.
Худшая сложность случая - это O (n), но H2CO3 дает O (logn) как наихудшую сложность без объяснения причин. – vkaul11
Первый абзац этого блога противоречив. Он правильно указывает, что худшим случаем является рекурсивный вызов O (log n), но затем продолжает говорить, что он может делать вложенные рекурсивные вызовы O (n) .Какой из них? И второй абзац настолько легок в левом поле, что это непонятно. –
@JimMischel: блог, похоже, совершенно несовместим с худшей сложностью сложного места на месте быстрого сортировки. Наихудший случай - O (n), а средний случай - O (log n). – nhahtdh
Это интервью предполагает, что это O (п)
Нет, это не делает:
Решение: Quicksort имеет пространство сложность O (LogN), даже в худшем дело.
Это зависит от реализации алгоритма. Как поясняет статья wikipedia, есть две реализации: вы cna делаете простую реализацию с O (n) пространством и лучшей реализацией, которая использует только пространство O (logn) – Techmonk
Прочитайте полное решение «Версия quicksort с использованием локального разбиения только постоянное дополнительное пространство перед выполнением любого рекурсивного вызова. Однако, если он сделал вложенные рекурсивные вызовы O (logn), он должен хранить постоянный объем информации от каждого из них.Поскольку лучший случай делает не более, чем O (logn) вложенные рекурсивные вызовы, он использует O (logn). В худшем случае O (n) вложенные рекурсивные вызовы, и поэтому требуется O (n) пробел. » См. Ссылку Я отправил http://futur3googl3r.blogspot.com/2008/08/google-interview-questions.html – vkaul11
@Techmonk В статье также говорится, что «когда она выполнена тщательно» :) – 2013-02-22 23:30:50
Оба они * возможно * описывают один и тот же алгоритм (я не читал детали). O (n) * extra * space - это худший ** случай, а O (log n) * extra * space - ** средний **. – nhahtdh