タイトルは自明です。非常に簡単な質問です。私はそれがO(n)だと思うが、私の最後の明日の前に確認したい。C++ステートメントのBig-O 'delete [] Q;' O(1)またはO(n)?
答えて
短い答えは...それに依存します。
Q
がデストラクタを持つオブジェクトの配列へのポインタの場合、delete[] Q
はすべてのデストラクタを呼び出す必要があります。これはO(n)デストラクタを呼び出します。ここで、nは配列内の要素の数です。一方、Q
がデストラクタを持たないオブジェクトの配列(たとえば、int
sまたは単純なstruct
)を指している場合は、O(1)時間だけかかるデストラクタを呼び出す必要はありません。
これらのデストラクタはそれぞれO(1)で実行する必要はありません。オブジェクトが、例えば、std::vector
オブジェクトの場合、各デストラクタは順番に、より多くの割り当て解除を解除しなければなりません。これらのオブジェクトが何であるかを知らなければ、デストラクタが呼び出されると、デストラクタが些細な場合は0個のデストラクタが呼び出され、それ以外の場合はO(n)デストラクタが呼び出されます。
しかし、ヒープアロケータの仕組みの実装の詳細は無視されます。メモリブロックの割り当てを解除すると、O(ログK)時間がかかる可能性があります。ここでKは割り当てられたブロックの総数です。メモリのブロック数に関係なくO(1)時間かかる場合があります。 O(ログログK)など。アロケータがどのように動作するかを知らずに、あなたは正直にはわからない。つまり、ブロックをメモリアロケータに渡す前にオブジェクトをクリーンアップするために必要な作業のみに焦点を当てると、格納されているオブジェクトにデストラクタがある場合はO(n)デストラクタ、それ以外の場合は0デストラクタが呼び出されます。これらのデストラクタは、完了までに時間がかかりません。次に、メモリブロックをメモリアロケータに再導入するコストがかかります。メモリアロケータには時間がかかることがあります。
希望すると便利です。
@エタンバロンはこれをクリーンな紙に書いています。あなたのシャツの下に置く。質問紙が渡されているので、迅速に動かして質問紙の下にあなたのシャツの下に紙を入れてください。がんばろう。 –
私は、多くの人が見逃している重要なことを追加したいと思います。配列に含まれるオブジェクトは、定義する必要はありません*デストラクタは必要ありません。重要なことは、デストラクタ(定義済みまたはデフォルト)が* trivial *であることです。つまり、クラスにメンバーとして 'ベクトル 'がある場合、デストラクタが明示的に定義されていなくても、デフォルトのデストラクタは重要ではなく、実行されます。 – Duncan
@templatetypedefこれはすばらしい答えです、ありがとうございます。 –
私はそれに賛同しますが、Xバイトのメモリを解放し、デストラクタを心配する必要はありません。
いくつかのメモリアロケータは、「小さな」(1〜500バイト)オブジェクトの空きリストを保持します。リストへの挿入はO(1)です。すべてのスレッドに対して1つの空きリストがある場合、ミューテックスを取得する必要があります。ミューテックスを取得するには、通常、最大2000個の "スピン"が必要で、システムコール(非常に高価です)が必要です。一部のアロケータは、スレッドローカルストレージを使用するスレッドごとに空きリストを持っているため、mutexは取得されません。
中規模(500〜60000バイト)のサイズのオブジェクトの場合、多くのアロケータはブロック結合を行います。つまり、隣接するブロックも空いているかどうかをチェックし、2つまたは3つの空きブロックを結合して1つ大きな空きブロックを作成します。合体はO(1)ですが、再びミューテックスを取得する必要があります。
大規模なブロックの場合、一部のアロケータはシステムコールを使用してメモリを取得します。したがって、メモリを解放することもシステムコールです。
- 1. O(1)、O(n log n)、O(log n)の複雑さを持つアルゴリズムの例
- 2. O(n)vs O(n^2)
- 3. Javaコレクション:TreeMap.size()およびTreeSet.size():O(1)またはO(n)?
- 4. ListBox.FindString最悪の場合のランタイムは何ですか? O(n)、O(n log n)、O(1)?
- 5. 実際には、リンクリスト追加O(N)またはO(1)ですか?
- 6. 漸近分析では、 - O(f(n)+ g(n))= O(max {f(n)、g(n)})
- 7. T(n)= 2T(n/2)+ O(n)からO(nlogn)を得る方法
- 8. なぜO(n * logn)ではなくTreeSet Iteration O(n)ですか?
- 9. O(log n)は常にO(n)よりも速いですか
- 10. O(n)とO(log(n))の違い - これはより良く、O(log(n))は正確に何ですか?
- 11. 時間Oの複雑さ(n(nはをログ)ログ)+ nはO(L)
- 12. C(+)でのO(1)ルックアップ
- 13. 防止O(N)クエリ
- 14. Big Oの例2^n
- 15. 範囲最小クエリ<O(n), O(1)>(ツリーから制限付きRMQへ)
- 16. C#逆シリアル化のO(n * n)の動作?
- 17. O(fib n)複雑アルゴリズム?
- 18. 可能な説明(N!)= O(NLG(N))
- 19. C++テキストファイルI/O
- 20. 合計アルゴリズム:O(n^2)平均で
- 21. O(3^log n)をO(n^log 3)として書き直すことはできますか?
- 22. 床(√2n)のO(log log n)アルゴリズム?
- 23. O(n^3)未満の最大フローアルゴリズム
- 24. ファイルI/Oコード(C++)
- 25. (Monad m、Monoid o)=> m o?
- 26. ランタイムをO(n)に減らす
- 27. このO(n^4)アルゴリズムは回避できますか?
- 28. O(LogN)== O(3LogN)ですか?
- 29. O(N)未満のN擬似乱数を生成する
- 30. f(n)= log(n)^ mはすべての自然数mに対してO(n)
私はあなたにヒントを与えます: 'std :: string ::〜string()' –
どのタイプが 'Q'ですか? –
密接に関連しています:http://stackoverflow.com/q/16420357/179910 –