java - マップに挿入する前に文字列内の各文字をループする Big O 表記

Question

私は大きな O 記法に不慣れで、私のプログラムでそれについていくつか質問があります。

私は2つのマップを持つプログラムを持っています。マップの 1 つに追加する前に、各キャラクターをループして、大文字と小文字をランダムに変更します。文字列を他のマップに入れるだけです（操作なし）

マップへの挿入の大きな O が O(1) である場合、マップに挿入する前に各文字をループするとどうなりますか? このプログラムの全体的な複雑さはどのくらいになりますか (マップへの各挿入を組み合わせると)?

Answer 1

サイズ n の文字列があり、それを反復処理して、内側のループで O(1) 挿入を実行すると、時間計算量は O(n) になります。

これをもう少し簡単にするために、挿入コストがa ( aは n の関数、定数、またはまったく別のものである可能性がある) と仮定すると、総コストは O(an+a) になります。これは、内側のループで n 回挿入を行ってから、文字列全体に対してさらに 1 回挿入を行っているためです。あなたの場合、a=1 なので、O(1n+1) = O(n) となります。