Beste svaret
Mergesort, hvis det implementeres for å lage matriser i rekursive samtaler, vil skape mange av dem, men de vil ikke eksistere samtidig. I hvert rekursivt anrop lager du en matrise (eller 2 avhengig av en implementering) for sammenslåing, og de tar ikke mer enn O (n) plass, og deretter når sammenslåingen er ferdig, blir disse matriser slettet, og noen nye vil bli opprettet etter et øyeblikk i et annet rekursivt anrop. Hvis du teller hvor mye plass alle matriser som noensinne har blitt opprettet tok, ville det være O (n log n), men du trenger ikke å bry deg om denne informasjonen – du trenger ikke mer enn O (n) plass, for når du trenger å lage en matrise, eksisterer ikke alle andre lenger og har ikke noe minne . Merk at du ganske enkelt kan erklære 2 – eller 3 – matriser i begynnelsen, hver lengde på n, og deretter lagre sekvensen i en av dem, mens du bruker den andre til å slå sammen, vil det forbedre ytelsen og vise deg utover tviler på at det ikke er behov for mer enn O (n) minne.
Svar
Ved sammenslåing av sortering når vi slår sammen den 2 sorterte matrisen lager vi 2 midlertidige matriser. L [ ] = Arr [venstre, midt] (venstre matrise) for å midlertidig lagre den gamle matrisen fra venstre til midten (sortert venstre halvdel) og R [] = Arr [midt + 1, høyre] (høyre matrise) for å midlertidig lagre den gamle matrisen fra midten + 1 til høyre (sortert til høyre halvdel), så slår vi sammen de to midlertidige gruppene til den opprinnelige. Det faktum at vi lager 2 midlertidige matriser for å lagre tallene til den opprinnelige matrisen, siden den opprinnelige matrisen har n elementer den midlertidige matriser har henholdsvis størrelse n og dermed den ekstra plassen til n og en O (n) romkompleksitet. Det opprinnelige rommet til matrisen blir ikke tatt med i beregningen av romkompleksiteten til en ing-algoritme.