Nejlepší odpověď
Mergesort, pokud je implementován k vytvoření polí v rekurzivních voláních, vytvoří mnoho z nich, ale nebudou koexistovat současně. V každém rekurzivním volání vytvoříte pole (nebo 2 v závislosti na implementaci) pro sloučení a nezabere více než O (n) prostor a poté, když se sloučení je hotovo, tato pole jsou smazána a některá nová budou po chvíli vytvořena v nějakém jiném rekurzivním volání. Pokud jste spočítali, kolik místa zabrali všechna pole, která kdy byla vytvořena, bude to „O (n log n), ale nemusíte se o tyto informace starat – nepotřebujete více než O (n) prostor, protože když potřebujete vytvořit pole, všechny ostatní již neexistují a nezabírají žádnou paměť . Všimněte si, že na začátku můžete jednoduše deklarovat 2 – nebo 3 – pole, každé o délce n, a poté uložit sekvenci do jednoho z nich, zatímco pro sloučení použijete druhé, zlepší to výkon a ukáže vám to i za pochybuji, že není potřeba více než O (n) paměti.
Odpověď
Při slučování třídění, když slučujeme 2 seřazené pole, vytvoříme 2 dočasné pole. L [ ] = Arr [vlevo, uprostřed] (levé pole) k dočasnému uložení starého pole zleva do středu (seřazené levé polovině) a R [] = Arr [střední + 1, vpravo] (pravé pole) k dočasnému uložení starého pole od poloviny + 1 doprava (seřazeno na pravou polovinu), potom spojíme dvě dočasná pole do původního. Skutečnost, že vytvoříme 2 dočasné pole pro uložení čísel původního pole, protože původní pole má n prvků dočasného pole mají velikost n, a tedy i extra prostor prostoru n a složitost prostoru O (n). Původní prostor pole se při výpočtu prostorové složitosti druhu nezohledňuje. algoritmus.