有多少陣列訪問以下

我有以下問題。給波浪線逼近陣列的數量爲以下代碼訪問有多少陣列訪問以下

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

但是，我無法弄清楚到底有多少數組訪問有，在N

而言，我想答案會n^3 - n，用於A和n^2兩種B和C.

我似乎是在右邊粘性？

2016-10-10 jroy8

的N階爲大O符號N^2。

這是由於2嵌套for循環。

2016-10-10 19:01:00 UserF40

因此，有N^2數組訪問你在說什麼？ – jroy8

如果我們假設沒有編譯器/ JIR優化，我們有：

1）所有陣列具有訪問

2相同的量）第二個用於執行〜I/2倍

3）總和（I = 0，i = N時）1/2 = O（N^2）（第一n個自然數的總和）

2016-10-10 19:10:45 olsli

因此，數組訪問的次數是你的要點3）？ – jroy8

是的，總金額爲O（n^2） – olsli

否，則不能指望這樣的

你的數組A []被訪問次數與B []和C []相同，唯一的區別是A在i位置訪問j次。

和其他的東西，是不是N3，你不能做次B，你應該分析這兩種for`s計算複雜

所以，首先爲執行n次，第二個用於執行n/2倍

在這種情況下，你有O(nˆ2/4)或只是O(nˆ2)

2016-10-10 19:59:35

OH好是有道理其實，我不明白這一點的唯一的事情就是你去'爲O（n^2/4）'應該不會是' O（n^2/2）'？ – jroy8

發生這種情況是因爲你正在使用自然數，例如，對於n = 1和n = 2。在第二個循環中有1個交互作用。因此，一半的交互作用是相同的。在這種情況下（N * N/2）/ 2 –

回答