タイトルは自明です。とても簡単な質問です。O(n) だと思いますが、明日のファイナルの前に確認したかったのです。
質問する
2002 次
2 に答える
18
短い答えは... それは依存します。
Qがデストラクタを持つオブジェクトの配列へのポインタである場合delete[] Q、それらのデストラクタをすべて呼び出す必要があります。これにより、O(n) デストラクタが呼び出されます。ここで、n は配列内の要素の数です。一方、Qがデストラクタを持たないオブジェクトの配列 (たとえば、ints または単純なstructs) を指している場合、デストラクタを呼び出す必要はなく、O(1) 時間しかかかりません。
これらのデストラクタは、それぞれ O(1) 時間で実行する必要がないことに注意してください。オブジェクトがたとえばオブジェクトの場合、std::vector各デストラクタはさらに多くの割り当て解除を実行する必要があります。これらのオブジェクトが何であるかを詳しく知らなくても、デストラクタが呼び出された場合、デストラクタが自明な場合は 0 個のデストラクタが呼び出され、それ以外の場合は O(n) 個のデストラクタが呼び出されるということしか言えません。
しかし、これはヒープ アロケータの動作方法の実装の詳細を無視しています。メモリ ブロックの割り当て解除に O(log K) 時間かかる可能性があります。ここで、K は割り当てられたブロックの総数です。または、メモリ ブロックの数に関係なく O(1) 時間かかるか、またはO(log log K) などです。アロケータがどのように機能するかを知らなければ、正直なところ確信が持てません。
つまり、ブロックをメモリ アロケータに戻す前にオブジェクトをクリーンアップするために必要な作業だけに集中すると、格納されているオブジェクトにデストラクタがある場合は O(n) 個のデストラクタが呼び出され、それ以外の場合は 0 個のデストラクタが呼び出されます。これらのデストラクタは、完了するまでにかなりの時間がかかる場合があります。次に、メモリのブロックをメモリ アロケータに再導入するコストがかかりますが、これには時間がかかる場合があります。
お役に立てれば！
于 2013-05-09T21:59:34.627 に答える