Legjobb válasz
Az egyesítés akkor hoz létre, ha a rekurzív hívások tömbjeinek létrehozására szolgál. sok közülük, de nem fognak egyszerre együtt létezni. Minden rekurzív hívásban létrehoz egy tömböt (vagy 2-t a megvalósítástól függően) az összevonáshoz, és legfeljebb O (n) helyet foglalnak el, majd az összevonáskor kész, ezek a tömbök törlődnek, és néhány új rekurzív hívás egy pillanat múlva létrejön. Ha megszámolta, hogy az összes létrehozott tömb mekkora helyet foglal el, akkor ez “d” O (n log n), de nem kell törődnöd ezekkel az információkkal – nem kell több, mint O (n) hely, mert amikor tömböt kell létrehoznod, akkor az összes többi már nem létezik, és nem foglalnak el semmilyen memóriát . Ne feledje, hogy az elején egyszerűen deklarálhat 2 – vagy 3 – tömböt, mindegyik n hosszúságú, majd az egyikben tárolhatja a sorrendet, míg a másikat egyesítésre használja, ez javítja a teljesítményt, és túlmutat rajta kétséges, hogy nincs szükség O (n) memóriánál többet.
Válasz
Az egyesítés rendezésében, amikor a 2 rendezett tömböt egyesítjük, 2 ideiglenes tömböt hozunk létre. L [ ] = Arr [balra, középre] (bal oldali tömb) a régi tömb ideiglenes tárolásához balról középre (rendezve a bal fele) és R [] = Arr [közepe + 1, jobbra] (jobb tömb) a régi tömb ideiglenes tárolásához közepétől + 1-től jobbig (rendezve a jobb fele), majd összeolvasztjuk a két ideiglenes tömböt az eredetire. Az a tény, hogy létrehozunk 2 ideiglenes tömböt az eredeti tömb számainak tárolására, mivel az eredeti tömbben n elem van, az ideiglenes tömb a tömbök n nagyságúak, ezért az n és az O (n) tér komplexitásának külön területe. A tömb eredeti terét nem veszik figyelembe, miközben kiszámítják egy fajta tér komplexitását algoritmus.