Minneskomplexitet

Grunder

Snabböversikt

Minneskomplexitet beskriver hur minnesanvändningen förändras när indata växer. Skilj på totalt minne, inklusive indata, och extra minne som algoritmen behöver utöver indata.

En sorteringsalgoritm som ändrar den befintliga arrayen kan ha O(1) extra minne även om själva arrayen använder O(n) utrymme.

Vad använder minnet?

• Indata: en array med n heltal kräver ett utrymme proportionellt mot n.
• Tillfälliga buffertar: en kopia av alla n värden ger O(n) extra minne.
• Anropsstack: rekursiva anrop tar plats även om koden inte skapar en ny array.
• Lokala räknare: ett fast antal variabler brukar vara O(1) extra minne.

Två implementationer i C#

C#

C# | InPlace.cs

static void DoubleInPlace(int[] values)
{
    for (int i = 0; i < values.Length; i++)
        values[i] *= 2;
}

C++

C++ | InPlace.cpp

#include <vector>
void doubleInPlace(std::vector<int>& values) {
    for (int& value : values) value *= 2;
}

Metoden ändrar samma array och har O(1) extra minne.

C#

C# | Copy.cs

static int[] DoubledCopy(int[] values)
{
    int[] output = new int[values.Length];
    for (int i = 0; i < values.Length; i++)
        output[i] = values[i] * 2;
    return output;
}

C++

C++ | Copy.cpp

#include <vector>
std::vector<int> doubledCopy(const std::vector<int>& values) {
    std::vector<int> result;
    result.reserve(values.size());
    for (int value : values) result.push_back(value * 2);
    return result;
}

Här skapas en ny array. Därför behövs O(n) extra minne.

Rekursion och anropsstack

Rekursiv binärsökning kan kräva O(log n) stackminne, medan en iterativ version kan använda O(1) extra minne. Anropsdjup räknas också.

Analysera tid och minne var för sig

Båda metoderna besöker samtliga element och tar därför O(n) tid. Minneskostnaden skiljer sig åt.

Livslängd och ägarskap spelar roll

En tillfällig array räknas som extra minne även om den senare tas bort. Indatasamlingen räknas ofta inte in när vi analyserar hjälpminne (auxiliary space). Skriv därför vilken definition som används. En funktion som skapar ett nytt resultat med n värden behöver normalt minne proportionellt mot n.

Rekursion eller iteration

Rekursiv kod kan se kort ut, men varje aktivt metodanrop använder en stackram. Linjär rekursion kan därför kräva O(n) extra stackminne även utan nya arrayer. En iterativ version kan ibland nöja sig med O(1) extra utrymme.

Verklig minnesanvändning

Objekt har overhead och dynamiska arrayer kan reservera mer kapacitet än de använder. I .NET påverkar även garbage collection. Använd både komplexitetsanalys och minnesprofilering när prestanda faktiskt spelar roll.

Läs vidare

↗Extern referensGeeksforGeeks: Space ComplexityUndersök hur minnesbehovet växer.

• Mergesortering med buffert

Andra familjer av minneskomplexitet

Två användbara klassificeringar beskriver familjer av minnesgränser snarare än en enda tillväxtfunktion.

Polylogaritmiskt minne: O((log n)^c)

För en fast positiv konstant c innebär O((log n)^c) att extra minne växer som en bestämd potens av logaritmen. En tabell med ungefär log₂(n) rader och log₂(n) kolumner tar exempelvis O((log n)²) celler. O(log n) är specialfallet c = 1. För varje fast ε > 0 växer (log n)^c asymptotiskt långsammare än n^ε. Konstanten c får inte växa med indatan.

int side = (int)Math.Log2(n) + 1; // n >= 1
int[,] workspace = new int[side, side]; // O((log n)^2) celler

Polynomiskt minne: O(n^c)

För en fast konstant c >= 0 är polynomiskt minne en hel familj O(n^c). Här ingår konstant (c = 0), linjärt (c = 1), kvadratiskt (c = 2) och kubiskt (c = 3) minne. En tvådimensionell n × n-matris är kvadratisk, medan en tredimensionell n × n × n-array är kubisk. Exponenten måste vara en fast konstant; om den växer med indatan är det inte längre polynomiskt minne enligt denna definition.

Dessa termer beskriver minnesbehov, inte antalet CPU-operationer. Se komplexitetskartan för exempel på de enskilda klasserna.