for (int i = 0; i < n / 2 1; i ) {
for (int j = i; j < n; j ) {
}
}
這個例子的復雜性是什么？知道這一點的快速計算是什么？n是陣列長度。
uj5u.com熱心網友回復：
計算您執行的迭代次數。
- 在外回圈的第一遍中，您執行內回圈的 n 個回圈
- 第二個是 n - 1
- 這一直持續到外回圈
i為 n / 2 且內回圈為 n - n/2 次。
因此總迭代次數為：n n - 1 .. n - n/2 = n * (n/2 1) - (n/2) * (n/2 1)/2 = 3 * n * n/8 3 * n/4
因此復雜度函式是3*n*n/8 3*n/4，它是 O(n^2) 的成員（也是 tetha(n^2)）
編輯：在我做的計算中，我使用公式 1 2 3 .. n = n*(n 1)/2，至少對我來說，這是我心里知道的，但被推斷為高斯公式。
uj5u.com熱心網友回復：
我認為解釋它的最簡單方法如下：
外回圈運行近一半 n 次，并且對于至少n/2次迭代，內回圈至少運行n次。因此，內部回圈迭代的總數至少為n * n/2，即O(n^2)
uj5u.com熱心網友回復：
當您雙擊n，迭代的金額將次4.
當你三倍n，迭代的金額將時間9
...
=> 復雜度為 O(n^2)。
uj5u.com熱心網友回復：
其他答案沒有錯，但是如果您編譯了這個并嘗試測量 的不同值的執行時間n，則無論 的值如何，您都可能得到相同的結果n。
這是因為，根據優化設定，編譯器可能會認識到這些回圈中沒有發生任何事情，這在它們完成后會產生任何影響。因此，可以完全優化回圈。參見例如https://godbolt.org/z/bc9Mzr7db。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/407548.html
標籤：
上一篇：開關函式是否應該將我試圖復制的陣列更改為另一個陣列并進行細微更改？
下一篇：C中函式的靈活性