スタッキングコンテナのBig O

Question

アクセスのために時間複雑度O（log（N））を持つred-blackツリーとして実装されたstd :: mapを使用します（このサイトによれば：http://bigocheatsheet.com/）。これらのコンテナを積み重ねると、大きなOをどのように計算するのですか？

たとえば、map<int, map<int, int>>です。一番内側の地図にアクセスするための大きなOは何ですか？

Answer 1

あなただけだから、O（LOGN） + O（LOGN） = O（klogn） = O（LOGN）です

map<int, map<int, int>> data; 
const auto& lookup = data[5]; // here you spend O(logn) 
int value lookup2 = lookup[3]; // here you spend O(logn) 

、この場合には複雑さを合計する必要があります。

ネストされたレベルの量はNには依存しませんが、彼らは常に一定であるので、これはO（LOGN）ようにmap<int, map<int, map<int, map<int, ..とした場合のもだろう。

Answer 2

それでもO(Log(N))

あなたが出てマップ内の第2のマップにアクセスする意味と仮定すると、それが背中合わせに基本的に2つのO（ログ（N））の操作です。したがって、O(2*log(N))は減少し、再びO(log(N))になります。

Answer 3

O（log（N））と同じです。

これは、「内部」マップを取得するためにO（log（N））を持っているため、この要素に対してO（log（N））を再度必要とするため、 N））であり、O（log（N））と同じである。

Answer 4

同じもの。 map<int, map<int, int>> mを持っていて、m[4][2]を検索したい場合、これは2つの独立したマップ検索です。したがって、それらを追加するだけです。O(log M + log N) = O(log MN)Mは外側のマップのサイズで、Nは内側のマップのサイズです。

外側と内側のマップサイズは独立していることに注意してください。