I次のコードを持って機能の成長の順序を表示
int sum = 0;
for (int i = 1; i <= n; i = i*2)
{
for (int j = 1; j <=n; ++j)
{
++sum;
}
}
そして私の答えが正しいにもかかわらず、一部の人々に応じて以下の分析が間違っているが、私は理由を理解していない持っています。
だから、私は、次のよう
n = 1; i = 1; j is being executed 1 time
n = 2; i = 2; j is being executed 2* 1 time
n = 3; i = 4; j = 4 * 3 times
n = 4; i = 8; j = 8 * 4 times
n = 5; i = 16; j = 16 * 5 times
......
n = k; i = 2^k; j = n * 2^k times
そして2^kは、ログ(n)が
あるので、この関数の成長のためにはlinearithmic成長率である(n)をnlogされません。
分析に何か間違っていますか?それは私がたくさん混乱しているので、私は間違いがあるかどうか私に知らせてください。ありがとうございました!この分析をより複雑なネストループに適用したいが、それを行う前に、私が間違っていることを知る必要がある。
更新:私は自分の分析が間違っている理由を理解しようと多くの時間を費やしました。 @ YvesDaoustのおかげで、もう少し理解し始めたと思う。
についてありますコード。コードをテキストとして投稿します。 – khelwood
外部ループは 'log n'、内部ループは' n' –
@PeterLawrey外部ループはlognで内部ループはnであると理解していますが、解析を作成してみることができますより複雑なネストループに適用します。 – Student