次の配列へのアクセス数

次の質問があります。アレイの数は、次のコード次の配列へのアクセス数

for (int i=0; i < n; ++i) 
    for (int j = i/2; j < i; ++j) 
     A[i] = B[j] + C[j];

のためにアクセスするしかし、私はN

の面で、ある正確にどのように多くの配列がアクセスを見つけ出すことはできませんと私は答えは思っためチルダ近似を与えますn^3 - Aはn、BとCはn^2です。

私は右のタックにいるようですか？

2016-10-10 jroy8

大きなO表記の場合、N次はN^2です。

これは2つのネストされたループによるものです。

2016-10-10 19:01:00 UserF40

だからN^2の配列は、あなたのことわざにアクセスがありますか？ – jroy8

我々は何のコンパイラ/ JIRの最適化が存在しないと仮定した場合、我々は持っている：

1）すべてのアレイは

2にアクセスするのと同じ量を持っている）は、第2〜I/2回

行われるため

3）合計（I = 0、I = N）I/2 = O（N^2）（最初のn個の自然数の和）

2016-10-10 19:10:45 olsli

配列アクセス数はあなたのポイントです3）？ – jroy8

はい、合計金額はO（n^2） – olsli

いいえ、あなたはその

のように数えることができません

あなたの配列A [] B []とC []と同じ時刻にアクセスしていますが、唯一の違いはAが回アクセスiの位置にあることです。

および他の事、n3はないが、あなたは時間Bを行うことはできません、あなたはn回実行する第一なので、複雑

をカウントするために、両方のfor`sを分析する必要があり、実行n/2回秒この場合

あなたは O(nˆ2/4)持っているか、単に O(nˆ2)

2016-10-10 19:59:35

です。実際には意味がありますが、私がそれを得られない唯一のことは、あなたが 'O（n^2/4） O（n^2/2） '？ – jroy8

これは、自然数を使って作業しているために起こります。たとえば、n = 1、n = 2の場合は、2番目のループで1回の対話が行われます。この場合、インタラクションの半分は同じです。/2）/ 2 –

答えて