-1

例としては、相互に存在しない2つのforループがあります。それでも0（n）に等しいですか。また、文字列を送信するStringbuilderコンストラクターの時間計算量について質問する理由もあります。

4

4 に答える 4

0

時間計算量の質問：

アルゴリズムがO（n）であると言うことは、そのアルゴリズムが最大でn * kステップを取ることを意味します。ここで、nは入力サイズであり、kは任意の定数です。したがって、アルゴリズムがnステップ、2nステップ、（1/2）nステップ、100nステップ、または1000000nステップのいずれをとるかは関係ありませんが、それでもO（n）です。

したがって、2つのO（n）アルゴリズムがある場合、それぞれに定数kがあり、nに関して実行するステップ数（たとえば、k1*nとk2*n）が得られます。両方のアルゴリズムを実行する場合、実行するステップ数は次のとおりです。

k1 * n + k2 * n

それは次と同じです：

（k1 + k2）* n

...nは公約数であるため。また、k1もk2もnとともに成長しないため（定数であるため）、それらの合計k1+k2はnとともに成長しません。つまり、k1 + k2は依然として定数であるため、実行時間は依然としてnの定数倍です。

Stringbuilderの質問：

わかりませんが、もし私があなたなら、文字列の長さを増やしてコンストラクターを実行してみて、毎回どのくらいの時間がかかるかを確認します。文字列が大きくなったときにコンストラクターがどれだけ速く減速するかによって、複雑さが何であるかがわかります。

于 2012-10-18T04:26:35.470 に答える
0

StringBuilder内部的には、コンストラクター呼び出しと追加メソッド呼び出しでネイティブを使用します。これは、ループarraycopy(Object, int, Object, int, int)よりもはるかに効率的だと思います。2 for

于 2012-10-18T03:47:58.470 に答える
0

O（n）+ O（n）= O（n + n）= O（n）。実際、任意の（有限）定数kに対してO（k * n）= O（n）です。

しかし、実際のプログラミングの問題では、O（n）の考慮事項は、通常、関係する係数よりもはるかに重要ではありません。係数が大きいO（n）アルゴリズムは、係数が小さいO（2 n ）アルゴリズムよりも実際にははるかに悪い場合があります。

問題のサイズの見積もりと一緒にコードの代替案を投稿し、どちらがより効率的かを尋ねる方がはるかに良いでしょう。

于 2012-10-18T03:48:14.083 に答える
0

質問が不明確です。

しかし、あなたが意味するのであれば、2つのO（n）が次々にコード化され、それでもO（n）です。

Lim (2*n/n) = 2 (constant).
n->INF

したがって、O（N）は上限と下限の両方であり、theta(N) => O(n)

于 2012-10-18T03:51:19.687 に答える