Давайте возьмем эту реализацию сортировки слиянием в качестве примера
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) или хуже.