Почему QuickSort использует O (log (n)) дополнительное пространство?
Я реализовал ниже алгоритм быстрой сортировки. Интернет Я читал, что у него есть потребность в пространстве O (log (n)). Почему это так? Я не создаю никаких дополнительных структур данных.
Это потому, что моя рекурсия будет использовать дополнительное пространство в стеке? Если это так, возможно ли это сделать с меньшим объемом памяти, не имея его рекурсивного (вместо этого сделать его итеративным)?
private static void quickSort (int[] array, int left, int right) {
int index = partition(array, left, right);
//Sort left half
if (left < index - 1)
quickSort(array, left, index - 1);
//Sort right half
if (index < right)
quickSort(array, index , right);
}
private static int partition (int array[], int left, int right) {
int pivot = array[(left + right) / 2]; //Pick pivot point
while (left <= right) {
//Find element on left that should be on right
while (array[left] < pivot)
left++;
//Find element on right that should be on left
while (array[right] > pivot)
right--;
//Swap elements and move left and right indices
if (left <= right) {
int temp = array[left];
array[left] = array[right];
array[right] = temp;
left++;
right--;
}
}
return left;
}
Ответы
Ответ 1
Исправить, дополнительное пространство - это фреймы кадров журнала (n). Из статьи Википедии Quicksort:
Существует более сложная версия, в которой используется отдельный раздел алгоритм и может достичь полной сортировки с использованием пространства O (log n) (не подсчет ввода) в среднем (для стека вызовов).
Кроме того, я думаю, что сделать его итеративным невозможно, потому что это не хвост рекурсивный.
Наконец, как указывали другие ответы, O (log (n)) для практически всех практических приложений очень и очень мала. Каждый постоянный фактор, как и накладные расходы вашей структуры данных, будет иметь большее влияние на использование памяти.
Ответ 2
Чтобы избавиться от рекурсивного вызова, вам придется использовать стек в вашем коде, и он все равно будет занимать пробел log(n).
Ответ 3
Если вы читаете далее в статье в Википедии, вы найдете более подробное обсуждение сложности пространства. В частности, они пишут:
Quicksort с локальным и нестабильным разделением использует только постоянное дополнительное пространство перед выполнением любого рекурсивного вызова. Quicksort должен хранить постоянный объем информации для каждого вложенного рекурсивного вызова. Поскольку лучший случай делает не более O (log n) вложенных рекурсивных вызовов, он использует O (log n). Однако без использования Sedgewick для ограничения рекурсивных вызовов в худшем случае quicksort может сделать O (n) вложенные рекурсивные вызовы и O (n) вспомогательное пространство.
Практически говоря, O (log n) память ничего. Например, если вам нужно сортировать 1 миллиард ints, для их хранения потребуется 4 ГБ, но для стека потребуется всего около 30 кадров стека, например, 40 байтов, а значит, около 1200 байт.
Ответ 4
Да, это из-за кадров стека, и да, может быть возможно преобразовать его в итеративный алгоритм, делая что-то очень умное (хотя ничто не приходит сразу ко мне). Но почему? O (log (n)) - почти ничего. Для справки, даже если у вас есть массив максимального размера, разрешенный Java, это 2 ^ 31 элемента, что составляет около 8 ГБ. Для Quicksort потребуется 31 стек кадров. Баллпарк, может быть, 100 байт за кадр? Итак, всего 3 КБ, что ничто по сравнению с памятью для фактического массива.
В действительности, почти в любое время что-то есть O (log (n)), он почти такой же, как и константа.
Ответ 5
Извините за возрождение этого старого вопроса, но я просто нашел совершенно другой (но немного глупый) ответ на ваш вопрос, planetmath.org
Любой алгоритм сортировки, который работает с непрерывным массивом, требует дополнительного пространства O (log n), так как это число укуса [sic], необходимое для представления индекса в массив.
