c++ - 空の std::map に N 個のアイテムを挿入する複雑さ

Question

次の関数の複雑さを知りたいです。
std::map は赤黒木として実装されており、挿入の複雑さは O(logN) であることを知っています。
しかし、空のマップに N 個のアイテムを追加し続ける場合、どのように計算できますか?

void add(int N, std::map<int, int>& map) {
  for (int i = 0; i < N; ++i) {
    map[i] = i;
  }
}

前もって感謝します、

Answer 1

RBツリーは一種の平衡二分木です。挿入操作は、基本的に挿入位置を見つけ、新しく挿入されたノードにスペースを割り当て、ポインターを調整してから、RBツリーのバランスを取り直します。挿入の複雑さはO（logN）です。

あなたの場合、最初に特定の操作の複雑さを決定します。これはlog（N）の複雑さで挿入され、次に操作が使用された回数を調べます。そのため、N（logN）があります。O（logN）は、コンテナー内の要素の数に関して使用される時間の増加の順序が最大でlogNの順序であることを意味します。実際に使用された時間がlogNであるという意味ではありません。

unordered_mapアプリケーションが時間計算量である場合、挿入時間の複雑さは一定であるため、使用を検討することができます。intからintにマッピングしているので、この場合はunordered_mapを使用してもまったく問題ありません。

ところで：あなたの数式では、log0は定義されていません。挿入する要素がない場合、挿入操作は実行されません。

Answer 2

あなたは合理的な質問をしています。

空で始まったツリーに N 個の項目を挿入すると、log(0) から開始して log(N) に進みます。つまり、全体の平均は実際log(N/2)には ではありませんlog(N)。

対数の場合、実際には違いはありません。全体的な複雑さは依然として対数です。あなたがしたことは、実際には対数の底を変更したことです。

Answer 3

O(log N) のことを N 回実行しているので、O(N log N) です。