Laten we deze implementatie van Merge Sort als voorbeeld nemen
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);
a) De tijdscomplexiteit van deze samenvoegsortering is O(n lg(n)). Zal het parallelliseren van (1) en (2) enige praktische winst opleveren? Theoretisch lijkt het erop dat je na het parallelliseren ervan ook in O(n lg(n))terecht zou komen. Maar kunnen we praktisch winst behalen?
b) Ruimtecomplexiteit van deze samenvoeging. Sorteer hier is O(n). Als ik er echter voor kies om samenvoegsortering ter plaatse uit te voeren met behulp van gekoppelde lijsten (niet zeker of dit redelijkerwijs kan worden gedaan met arrays), wordt de ruimtecomplexiteit O(lg(n)), aangezien u om rekening te houden met de framegrootte van de recursiestapel?
Kunnen we O(lg(n))als constant behandelen omdat het niet meer dan 64 kan zijn? Ik heb dit misschien op een paar plaatsen verkeerd begrepen. Wat is precies de betekenis van 64?
c) Sorteeralgoritmen vergeleken – Cprogramming.comzegt dat samenvoegen sorteren vereist constante ruimte met behulp van gekoppelde lijsten. Hoe? Hebben ze O(lg(n))constant behandeld?
d) Toegevoegd om meer duidelijkheid te krijgen.Is het voor de berekening van de ruimtecomplexiteit redelijk om aan te nemen dat de invoerarray of lijst zich al in het geheugen bevindt? Wanneer ik complexiteitsberekeningen doe, bereken ik altijd de “Extra” ruimte die ik nodig heb naast de ruimte die al door invoer is ingenomen. Anders zal de complexiteit van de ruimte altijd O(n)of erger zijn.
Antwoord 1, autoriteit 100%
a) Ja – in een perfecte wereld zou je log n merges moeten doen met de grootte n, n/2, n/4 … (of beter gezegd 1, 2, 3 … n/4, n/2, n – ze kunnen niet worden geparalleliseerd), wat O(n) oplevert. Het is nog steeds O(n log n). In een niet zo perfecte wereld heb je geen oneindig aantal processors en context-switching en synchronisatie compenseert eventuele voordelen.
b) Ruimtecomplexiteit is altijd Ω(n) omdat je de elementen ergens moet opslaan. Extra ruimtecomplexiteit kan O(n) zijn in een implementatie die arrays gebruikt en O(1) in implementaties van gekoppelde lijsten. In de praktijk hebben implementaties die lijsten gebruiken extra ruimte nodig voor lijstaanwijzers, dus tenzij je de lijst al in het geheugen hebt, zou het niet uit moeten maken.
bewerken
als je stackframes telt, dan is het O(n)+ O(log n) , dus nog steeds O(n) in het geval van arrays. In het geval van lijsten is het O(log n) extra geheugen.
c) Voor lijsten hoeven slechts enkele verwijzingen te worden gewijzigd tijdens het samenvoegproces. Dat vereist constant extra geheugen.
d) Dat is de reden waarom mensen in de analyse van de complexiteit van merge-sort noemen ‘extra benodigde ruimte’ of dat soort dingen. Het is duidelijk dat je de elementen ergens moet opslaan, maar het is altijd beter om ‘extra geheugen’ te noemen om puristen op afstand te houden.
Antwoord 2, autoriteit 91%
MergeSort time Complexiteit is O(nlgn), wat een fundamentele kennis is.
Samenvoegen Sorteerruimte complexiteit zal altijd O(n) zijn, ook met arrays.
Als je de ruimteboom uittekent, lijkt het alsof de ruimtecomplexiteit O(nlgn) is. Omdat de code echter een Depth First-code is, breidt u altijd slechts langs één tak van de boom uit, daarom zal het totale benodigde ruimtegebruik altijd worden begrensd door O(3n) = O(n).
Als u bijvoorbeeld de ruimteboom uittekent, lijkt het alsof het O(nlgn) is
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
waarbij de hoogte van de boom O(logn) is => Ruimtecomplexiteit is O(nlogn + n) = O(nlogn).
Dit is echter niet het geval in de eigenlijke code, omdat deze niet parallel wordt uitgevoerd. Bijvoorbeeld, in het geval waar N = 16, is dit hoe de code voor mergesort wordt uitgevoerd. N = 16.
16
/
8
/
4
/
2
/ \
1 1
let op hoe het aantal gebruikte ruimte 32 = 2n = 2*16 is < 3n
Vervolgens wordt het naar boven samengevoegd
16
/
8
/
4
/ \
2 2
/ \
1 1
dat is 34 < 3n.
Dan wordt het naar boven samengevoegd
16
/
8
/ \
4 4
/
2
/ \
1 1
36 < 16 * 3 = 48
dan wordt het naar boven samengevoegd
16
/ \
8 8
/ \
4 4
/ \
2 2
/\
1 1
16 + 16 + 14 = 46 < 3*n = 48
in een groter geval, n = 64
64
/ \
32 32
/ \
16 16
/ \
8 8
/ \
4 4
/ \
2 2
/\
1 1
wat 64*3 is <= 3*n = 3*64
Je kunt dit bewijzen door inductie voor het algemene geval.
Daarom wordt de complexiteit van de ruimte altijd begrensd door O(3n) = O(n), zelfs als u met arrays implementeert, zolang u de gebruikte ruimte na het samenvoegen opruimt en de code niet parallel maar sequentieel uitvoert.
Een voorbeeld van mijn implementatie wordt hieronder gegeven:
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;
}
Hopelijk helpt dit!=)
Binnenkort Chee Loong,
Universiteit van Toronto
Antwoord 3, autoriteit 3%
a) Ja, natuurlijk kan het parallelliseren van merge sort erg voordelig zijn. Het blijft nlogn, maar je constante zou aanzienlijk lager moeten zijn.
b) Ruimtecomplexiteit met een gekoppelde lijst moet O(n) zijn, of meer specifiek O(n) + O(logn). Merk op dat dat een + is, geen *. Houd je niet veel bezig met constanten bij het uitvoeren van asymptotische analyses.
c) In asymptotische analyse is alleen de dominante term in de vergelijking belangrijk, dus het feit dat we een + hebben en geen * maakt het O(n). Als we de sublijsten overal zouden dupliceren, zou dat O(nlogn)-ruimte zijn, maar een slimme op gekoppelde lijsten gebaseerde samenvoegsortering kan regio’s van de lijsten delen.
Antwoord 4, autoriteit 3%
Prestatie in het slechtste geval van samenvoegsortering: O(n log n),
Best-case prestatie van merge sort: O(n log n) typisch, O(n) natuurlijke variant,
Gemiddelde prestatie van samenvoegsortering: O(n log n),
Worst-case ruimtecomplexiteit van samenvoegsortering: О(n) totaal, O(n) hulp
Antwoord 5, autoriteit 3%
Eenvoudig en slim denken.
Totale niveaus (L) = log2(N).
Op het laatste niveau aantal knooppunten = N.
stap 1 :laten we aannemen dat voor alle niveaus (i) nodes = x(i).
stap 2 :dus tijdscomplexiteit = x1 + x2 + x3 + x4 + …. + x(L-1) + N(voor i = L);
stap 3 :feit weten we , x1,x2,x3,x4…,x(L-1) < N
stap 4 :dus laten we eens kijken naar x1=x2=x3=…=x(L-1)=N
stap 5 :Dus tijdscomplexiteit = (N+N+N+..(L)times)
Tijdscomplexiteit = O(N*L);
zet L = log(N);
Tijdcomplexiteit = O(N*log(N))
We gebruiken de extra array tijdens het samenvoegen dus,
Ruimtecomplexiteit: O(N).
Hint: Big O(x)-tijd betekent dat x de kleinste tijd is waarvoor we zeker kunnen zeggen met bewijs dat deze in gemiddeld geval nooit groter zal zijn dan x
Antwoord 6
complexiteit sorteerruimte samenvoegen is O(nlogn), dit is vrij duidelijk gezien het feit dat het maximaal kan gaan naar O(logn)-recursies en voor elke recursie daar is extra ruimte van O(n)voor het opslaan van de samengevoegde array die opnieuw moet worden toegewezen.
Voor degenen die O(n)zeggen, vergeet niet dat het O(n)is voor de framediepte van de reachstack.
Antwoord 7
voor zowel het beste als het slechtste geval is de complexiteit O(nlog(n)) .
hoewel er in elke stap extra N-grootte van de array nodig is, dus
ruimtecomplexiteit is O(n+n) is O(2n) omdat we de constante waarde verwijderen voor het berekenen van complexiteit, dus het is O(n)