Объединить время сортировки и пространственную сложность

Давайте возьмем эту реализацию сортировки слиянием в качестве примера

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

а) Временная сложность этой сортировки слиянием равна O (nlg (n)). Будет ли распараллеливание (1) и (2) практическим преимуществом? Теоретически, кажется, что после их распараллеливания вы также окажетесь в O (nlg (n). Но практически можем ли мы получить какие-либо выгоды?

б) Пространственная сложность этой сортировки слиянием здесь O (n). Однако, если я решу выполнить сортировку слиянием на месте, используя связанные списки (не уверен, что это можно сделать разумно с массивами), сложность пространства станет O (lg (n)), так как вы должны учитывать размер кадра стека рекурсии? Можем ли мы рассматривать O (lg (n)) как константу, поскольку она не может быть больше 64? Возможно, я неправильно понял это в нескольких местах. В чем конкретно значение 64?

c) http://www.cprogramming.com/tutorial/computersciencetheory/sortcomp.html говорит, что сортировка слиянием требует постоянного пространства с использованием связанных списков. Как? Они обрабатывали O (LG (N) константа?

d) [добавлено, чтобы получить больше ясности]. Для вычисления сложности пространства справедливо предположить, что входной массив или список уже находится в памяти? Когда я делаю вычисления сложности, я всегда вычисляю "дополнительное" пространство, которое мне понадобится, кроме пространства, уже занятого вводом. В противном случае сложность пространства всегда будет O (n) или хуже.

Ответы

Ответ 1

a) Да - в идеальном мире вам нужно будет делать log n слияния размера n, n/2, n/4... (или лучше сказано 1, 2, 3... n/4, n/2, n - они не могут быть распараллелены), что дает O (n). Это все равно O (n log n). В не очень совершенном мире у вас нет бесконечного числа процессоров, а контекст-коммутация и синхронизация компенсируют любые потенциальные выгоды.

b) Сложность пространства всегда Ω (n), поскольку вы должны где-то хранить элементы. Дополнительная сложность пространства может быть O (n) в реализации с использованием массивов и O (1) в реализациях связанных списков. На практике реализациям, использующим списки, требуется дополнительное пространство для указателей списков, поэтому, если у вас уже нет списка в памяти, это не имеет значения.

изменить если вы подсчитываете кадры стека, то это O (n) + O (log n), так что O (n) в случае массивов. В случае списков это O (log n) дополнительная память.

c) Списки требуют только некоторых указателей, измененных в процессе слияния. Это требует постоянной дополнительной памяти.

d). Поэтому в анализе сложности сортировки по объему люди упоминают "дополнительное пространство" или что-то вроде этого. Очевидно, что вам нужно хранить элементы где-то, но всегда лучше упомянуть "дополнительную память", чтобы держать пуристов в страхе.

Ответ 2

Время MergeSort Сложность - O (nlgn), которая является фундаментальным знанием. Слияние Сортировка сложности пространства всегда будет O (n), включая массивы. Если вы вычеркнете космическое дерево, будет казаться, что сложность пространства - O (nlgn). Однако, поскольку код - это код глубины первого, вы всегда будете только расширяться вдоль одной ветки дерева, поэтому требуемое общее использование пространства всегда будет ограничено O (3n) = O (n).

Например, если вы вычертите дерево пространства, похоже, что это O (nlgn)

                             16                                 | 16
                            /  \                              
                           /    \
                          /      \
                         /        \
                        8          8                            | 16
                       / \        / \
                      /   \      /   \
                     4     4    4     4                         | 16
                    / \   / \  / \   / \
                   2   2 2   2.....................             | 16
                  / \  /\ ........................
                 1  1  1 1 1 1 1 1 1 1 1 1 1 1 1 1              | 16

где высота дерева равна O (logn) = > Сложность пространства O (nlogn + n) = O (nlogn). Однако это не так в фактическом коде, поскольку он не выполняется параллельно. Например, в случае, когда N = 16, так выполняется код для mergesort. N = 16.

                           16
                          /
                         8
                        /
                       4
                     /
                    2
                   / \
                  1   1

Обратите внимание на то, сколько используется пробел 32 = 2n = 2 * 16 < 3n

Затем он сливается вверх

                           16
                          /
                         8
                        /
                       4
                     /  \
                    2    2
                        / \                
                       1   1

который равен 34 < 3n. Затем он сливается вверх

                           16
                          /
                         8
                        / \
                       4   4
                          /
                         2
                        / \ 
                       1   1

36 < 16 * 3 = 48

то он сливается вверх

                           16
                          / \
                         8  8
                           / \
                          4   4
                             / \
                            2   2
                                /\
                               1  1

16 + 16 + 14 = 46 < 3 * n = 48

в большем случае, n = 64

                     64
                    /  \
                   32  32
                       / \
                      16  16
                          / \
                         8  8
                           / \
                          4   4
                             / \
                            2   2
                                /\
                               1  1

который равен 64 * 3 <= 3 * n = 3 * 64

Вы можете доказать это индукцией для общего случая.

Следовательно, сложность пространства всегда ограничена O (3n) = O (n), даже если вы реализуете с массивами, пока вы очищаете использованное пространство после слияния и не выполняете код параллельно, но последовательно.

Пример моей реализации приведен ниже:

templace<class X> 
void mergesort(X a[], int n) // X is a type using templates
{
    if (n==1)
    {
        return;
    }
    int q, p;
    q = n/2;
    p = n/2;
    //if(n % 2 == 1) p++; // increment by 1
    if(n & 0x1) p++; // increment by 1
        // note: doing and operator is much faster in hardware than calculating the mod (%)
    X b[q];

    int i = 0;
    for (i = 0; i < q; i++)
    {
        b[i] = a[i];
    }
    mergesort(b, i);
    // do mergesort here to save space
    // http://stackoverflow.com/questions/10342890/merge-sort-time-and-space-complexity/28641693#28641693
    // After returning from previous mergesort only do you create the next array.
    X c[p];
    int k = 0;
    for (int j = q; j < n; j++)
    {
        c[k] = a[j];
        k++;
    }
    mergesort(c, k);
    int r, s, t;
    t = 0; r = 0; s = 0;
    while( (r!= q) && (s != p))
    {
        if (b[r] <= c[s])
        {
            a[t] = b[r];
            r++;
        }
        else
        {
            a[t] = c[s];
            s++;
        }
        t++;
    }
    if (r==q)
    {
        while(s!=p)
        {
            a[t] = c[s];
            s++;
            t++;
        }
    }
    else
    {
        while(r != q)
        {
            a[t] = b[r];
            r++;
            t++;
        }
    }
    return;
}

Надеюсь, что это поможет! =)

Вскоре Chee Loong,

Университет Торонто

Ответ 3

a) Да, конечно, распараллеливание сортировки слияния может быть очень полезным. Он остается nlogn, но ваша константа должна быть значительно ниже.

b) Сложность пространства со связанным списком должна быть O (n), а точнее O (n) + O (logn). Заметим, что a +, а не *. Не беспокойтесь о константах, когда делаете асимптотический анализ.

c) В асимптотическом анализе имеет место только доминирующий член в уравнении, поэтому тот факт, что мы имеем a +, а не a *, делает его O (n). Если бы мы дублировали подсписки во всем мире, я полагаю, что это будет O (nlogn) пространство - но сортировка слияния на основе интеллектуального связанного списка может совместно использовать регионы списков.

Ответ 4

Наихудшая производительность сортировки слияния: O (n log n), Наилучшая производительность сортировки слияния: O (n log n) типично, O (n) естественный вариант, Средняя производительность сортировки слияния: O (n log n), Сложность пространства с наименьшими размерами сортировки слияния: О (n) total, O (n) вспомогательный

Ответ 5

Космическая сложность: ее nlogn, если подрамник/сублист создается на каждом уровне (уровни logn * n пространства, требуемого на каждом уровне = > logn * n). И если нет, и рассматривается пространство стека, это будет logn для LinkedList и n (n + logn = n) для Array. Сложность времени: nlogn для худшего и среднего случая

Ответ 6

Сложность пространства сортировки слиянием - O(nlogn), это вполне очевидно, учитывая, что оно может достигать максимум O(logn) рекурсий, и для каждой рекурсии есть дополнительное пространство O(n) для хранения объединенного массива, которое необходимо переназначены. Для тех, кто говорит O(n) пожалуйста, не забывайте, что это O(n) для глубины кадра стека.

Ответ 7

как в лучшем, так и в худшем случае сложность O (nlog (n)). хотя дополнительный размер массива N требуется на каждом этапе, так Пространственная сложность - это O (n + n) - это O (2n), так как мы удаляем постоянное значение для вычисления сложности, так что это O (n)