有人可以幫我計算內回圈的時間復雜度嗎？據我了解，外部將是O（n）。但我不知道如何計算第二個里面發生了什么。
for (int i = 2; i < n; i ) {
for (int j = 2; i * j < n; j ) {
}
uj5u.com熱心網友回復：
對于“外回圈”的每次迭代，內回圈運行n/i時間
因此，其總復雜度將由下式給出：
n/2 n/3 n/4 ...
= n * (1/2 1/3 1/4 ...)
對于上面的右項，上限是 ln(n)
因此，此代碼的復雜度為O(n log n).
uj5u.com熱心網友回復：
內部回圈從2最多到但不包括n/i時間。您可以將其表示為n/i - 2。
如果我們運行內回圈n - 2次數（因為這是外回圈運行的次數），我們得到以下總和：
(n/2 - 2) (n/3 - 2) ... (3 - 2)
我有一種預感，但無法 100% 記得這個系列的總結log_e(n) * n或相似之處。因此，就時間復雜度而言，這變為O(log n * n).
uj5u.com熱心網友回復：
一旦 i * j ≥ n，即當 j = 上限（n / i）~ n / i 時，回圈就退出。從 j=2 開始，迭代次數為上限（n / i） - 1。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/422789.html
標籤：