Ich habe eine Frage, dass:Array Raum Komplexität
ich ein Array "S" haben die n Objekte in ihm hat. auch jedes Objekt hat m Felder. Ich möchte einige von ihnen in einem anderen Array wie "Q" speichern. Ich möchte wissen, dass die Raumkomplexität dieser einfachen Methode O(|Q|) ist?
Die Größe S ist n*sum(sizeofeach(m of n))
Dann nehme an, Sie r Objekt speichern, wo r<n
Die Größe q ist es r*(sum(sizeofeach(m of r))
Der Raum Komplexität der Menge an Speicherplatz benötigt wird Q zu speichern Lassen Sie s die Größe eines Elements in Q sein, dh . Die Raumkomplexität ist O(n*s). Wenn alle Felder dieselbe konstante Größe haben, könnte man sagen: O(n*m).
Also ist es nicht korrekt, O (r) zu schreiben? – user472221
Ich denke nicht, Komplexität wird für Speicherplatz verwendet, es wird für die Verarbeitungszeit verwendet. –
zum Beispiel die Raumkomplexität für merge sort ist O (n), die zum Speicherplatz gehört (glaube ich) – user472221