Der Titel ist selbsterklärend. Sehr einfache Frage. Ich denke, es ist O (n), aber wollte vor meinem Finale morgen überprüfen.
Die kurze Antwort ist ... es kommt darauf an.
Wenn Q ein Zeiger auf ein Array von Objekten ist, die Destruktoren haben, muss delete[] Q alle diese Destruktoren aufrufen. Dies ruft O (n) Destruktoren auf, wobei n die Anzahl der Elemente im Array ist. Wenn andererseits Q auf ein Array von Objekten zeigt, die keine Destruktoren haben (z. B. int s oder einfach struct s), müssen keine Destruktoren aufgerufen werden, was nur O ( 1) Zeit.
Beachten Sie, dass diese Destruktoren nicht jeweils in O (1) -Zeit ausgeführt werden müssen. Wenn die Objekte beispielsweise std::vector -Objekte sind, muss jeder Destruktor seinerseits weitere Deallokationen auslösen. Ohne mehr darüber zu wissen, was diese Objekte sind, können wir nur sagen, dass, wenn Destruktoren aufgerufen werden, 0 Destruktoren aufgerufen werden, wenn die Destruktoren trivial sind und O (n) Destruktoren andernfalls genannt werden.
Aber dies ignoriert die Implementierungsdetails, wie der Heap-Allokator funktioniert. Es ist möglich, dass die Freigabe eines Speicherblocks die O (log K) -Zeit benötigt, wobei K die Gesamtanzahl der zugewiesenen Blöcke ist, oder es kann O (1) dauern, unabhängig davon, wie viele Speicherblöcke es gibt, oder es könnte dauern O (log log K) usw. Ohne zu wissen, wie der Zuordner funktioniert, können Sie sich ehrlich gesagt nicht sicher sein.
Kurz gesagt, wenn Sie sich rein auf die Arbeit konzentrieren, die erforderlich ist, um die Objekte zu bereinigen, bevor Sie den Block an den Speicherzuordner übergeben, werden O (n) -Destruktoren aufgerufen, wenn die gespeicherten Objekte Destruktoren und 0 Destruktoren haben, die andernfalls aufgerufen werden. Diese Destruktoren benötigen möglicherweise eine nicht lange benötigte Zeit. Dann gibt es die Kosten für die Wiedereinführung des Speicherblocks zurück in den Speicherzuordner, die ihre eigene Zeit benötigen könnte.
Hoffe, das hilft!
Ich stimme zu, es hängt davon ab, aber lasst uns einfach über das Freigeben von X Bytes Speicher reden und sich nicht um Destruktoren kümmern.
Einige Speicherzuordner halten freie Listen für "kleine" (1 bis 500 Byte) Objekte bereit. Ein Einfügen in eine Liste ist O (1). Wenn es eine freie Liste für alle Threads gibt, muss sie einen Mutex erhalten. Der Erwerb eines Mutex beinhaltet normalerweise bis zu ein paar 1000 "Spins" und dann möglicherweise einen Systemaufruf (was sehr teuer ist). Einige Zuordner verfügen über freie Listen pro Thread, die lokalen Thread-Speicher verwenden, so dass sie kein Mutex-Acquire sind.
Bei einem mittelgroßen (500 bis 60000 Byte) großen Objekt blockieren viele Zuordner die Koaleszenz. Das heißt, sie prüfen, ob die angrenzenden Blöcke auch frei sind, und sie verschmelzen die 2 oder 3 freien Blöcke, um einen größeren freien Block zu bilden. Koaleszieren ist O (1), aber wieder muss es einen Mutex erhalten.
Bei großen Blöcken erhalten einige Zuweiser den Speicher über einen Systemaufruf. Das Freigeben des Speichers ist also auch ein Systemaufruf.
Tags und Links arrays c++ time-complexity big-o dynamic-memory-allocation