объединить пространство сортировки

При сортировке слиянием сверху вниз рекурсивные функции вызываются следующим образом:

void mergesort(Item a[], int l, int r) {
    if (r <= l) return;
    int m = (r+l)/2;
    mergesort(a, l, m);
    mergesort(a, m+1, r);
    merge(a, l, m, r);
}

В учебнике указано, что пространственная сложность этой стратегии равна O (n). тогда как если мы внимательно посмотрим на рекурсию: мы передаем указатель на массив в рекурсивных вызовах. Во-вторых, рекурсия решается в порядке обхода путем слияния нижних узлов с родительскими узлами. поэтому каждый раз в стеке находится O (logn) переменных (или O (log n) кадров в стеке). Так как же получилось, что сложность пространства O (n), несмотря на наличие методов слияния на месте?


sorting complexity-theory space-complexity
person mohit    schedule 03.08.2011    source источник
comment
Это не слияние по месту.   -  person Frank Q.    schedule 19.04.2012

Ответы (4)


arrow_upward
2
arrow_downward

Вы правы в том, что рекурсивные вызовы занимают пространство O (log n).

Но пространство, занимаемое самим массивом, равно O (n).

Общая сложность пространства составляет O (n) + O (log n).

Это O (n), потому что сверху оно ограничено (n) => 2 (n).

person Ray Toal    schedule 03.08.2011
comment
Для какого массива занято место? Я не вижу никакого массива, созданного в этой функции. Тот, который передается в сортировку слиянием, передается по ссылке. - person Frank Q.; 19.04.2012
comment
Тот факт, что функция не создает массив, не означает, что массива нет. Массив уже существует и занимает O (n) места. Обычно мы говорим о временной и пространственной сложности всего процесса, но да, если вы хотите быть очень разборчивым, тогда функция не добавляет O (n) пространства к существующему массиву, он добавляет только O (log n) для данных кадра стека. - person Ray Toal; 19.04.2012
comment
Я согласен с @FrankQ. Вход обычно не считается частью космической сложности. Вот почему, например, пузырьковая сортировка считается пространством O (1), а не O (n). - person Karan; 26.09.2012

arrow_upward
4
arrow_downward

Так как же получилось, что сложность пространства O (n), несмотря на наличие методов слияния на месте?

Потому что реализация, приведенная в вашей книге, вероятно, не использует технику слияния на месте. Если требуется сортировка по пространству O (1) и по времени O (n log n), heapsort обычно предпочтительнее сортировки слиянием, поскольку это намного проще. Только когда вы говорите о списках сортировки, сортировка слиянием O (1) имеет смысл ... и тогда это легко сделать. Сортировка слияния указана, например, для связанный список будет занимать O (1) пробел и O (n log n) время.

Фундаментальное недоразумение здесь, кажется, заключается в следующем: к алгоритмам относятся временные сложности, а не проблемы, которые они решают. Я могу написать сортировку слияния O (n ^ 3), если захочу ... не означает, что мой алгоритм не O (n ^ 3), и он ничего не говорит о вашем слиянии O (n log n) Сортировать. Это немного отличается от вычислительной сложности, о которой мы говорим, например, проблемы, находящиеся в P ... проблема в P, если для этого существует алгоритм с полиномиальным временем. Однако проблемы в P также могут быть решены с помощью алгоритмов с неполиномиальным временем, и если вы задумаетесь, построить такой алгоритм тривиально. То же самое и с космическими сложностями.

person Patrick87    schedule 03.08.2011

arrow_upward
1
arrow_downward

Как вы собираетесь хранить n предмет в log n пространстве? Это не имеет смысла. Если вы сортируете n элементы, O(n) пространство - лучшее, что вы можете получить.

person Brian Gordon    schedule 03.08.2011

arrow_upward
0
arrow_downward

Поскольку вы не выделяете никакого места внутри функции mergesort, кроме константы, сложность этого пространства равна O (lg (n)). Но ваша процедура слияния будет выделять память в случае массива, поэтому, учитывая это, она становится O (lg (n)) + O (n) = O (n). Если вы используете связанный список, вы можете избежать пустого места внутри процедуры слияния, поэтому лучше всего достигнете O (lg (n).

person Frank Q.    schedule 19.04.2012