假設存在具有I和J尺寸的2D矩陣。填補這一矩陣具有固定數量可以在兩個方式來完成：填充二維數組函數的順序是什麼？

首先，有兩個嵌套循環

for (int i=0;i<I;i++) 
{ 
    for (int j=0;j++;j++) 
    { 
     mat[i][j] = 123; 
    } 
}

這是O（N 2）通過書。

謝勝利：帶有單環

for(int k=0;k<I*J;k++) 
{ 
    mat[k/I][k % I] = 123; 
}

這是一個爲O（n）明顯

然而這兩種方法採取等於次以通過忽略環變種延遲來執行。

的更重要的標準：雙方執行完全相同的時間和順序

所以我們怎麼能說一個是O（N2），另一個是O（N）？

我們可以說這兩種方法都是O（n）嗎？

來源

2015-09-06 Zich

它看起來就像是我們應該找到謝勝利，一個每增長速度是O（N）根據確定的增長率，但第一個仍然棘手。 – Zich

這是一個爲O（n）明顯

不。循環的上界是I * J，使得這個O（n^2）。

來源

2015-09-06 15:11:43

好吧，假設我是1，循環就像一個普通的數組（一維），你會認爲這是一個o（n2），這個順序不應該被Data改變。對？ – Zich

是什麼讓上限變得重要？增長率應該是什麼情況呢？ – Zich

如果您正在填充4x4陣列，則在第一種情況下n = 4。4^2 = 16。需要16次迭代才能填充4x4陣列。在第二種情況下，n = 16。這將需要16次迭代來填充數組。

來源

2015-09-06 15:16:19 Todd

那麼這兩個訂單都是一樣的？你的回答沒有結論！ – Rassam

兩者都處理整個數組。似乎這裏的每個人都對這個問題感到困惑。這兩個都是O（n），因爲算法的性能直接關係到數據集的大小。換句話說，你迭代每一個項目一次。我認爲這個問題讓人們感到困惑，因爲它事實上表明，第一個是O（n2）。不是這樣。如果學生複製他們的確切作業問題，這樣真正的問題就不會在翻譯中丟失，這會更容易。我明白他們爲什麼不這樣做。 – Todd

不，你的理解是不正確的。在第二種解決方案中，你假設爲'n'實際上是m * n，即O（n^2）。

檢查循環變量k = I *∫（m和n在你的例子）

來源

2015-09-06 15:19:52

所以它的一個O（m * n）？和O（k）？我們有這樣的事情嗎？ – Zich

您可以將您的變量命名爲k，愛因斯坦，烏茲別克斯坦或任何其他任何東西，但不會改變任何內容。時間複雜度的大O符號表示什麼是順序，或大致需要多少操作來運行您的算法。O（n^2）表示它將進行m * n次操作（n^2，因爲當兩者都足夠大時，m和n會被比較）。 –

這兩種情況下的操作次數是相等的，所以我猜他們都有相同的順序，但足夠大？這是什麼意思？但我確信，變量的大小並不重要。 – Zich

填充二維數組函數的順序是什麼？

這是O（N 2）通過書。

這是一個爲O​​（n）明顯

回答

相關問題

這是一個爲O（n）明顯