爲什麼此循環返回值爲O（n log log n）而不是O（n log n）？

Question

考慮下面的C函數：

int fun1 (int n) 
{ 
    int i, j, k, p, q = 0; 

    for (i = 1; i<n; ++i) 
    { 
     p = 0; 

     for (j=n; j>1; j=j/2) 
      ++p; 

     for (k=1; k<p; k=k*2) 
      ++q; 
    } 
    return q; 
} 

的問題是決定哪些功能fun1最密切關注接近返回值？

（A）N^3
（B）N（logn）時間^ 2
（C）nlogn
（d）n日誌（logn）時間

這是其給出的解釋：

int fun1 (int n) 
{ 
    int i, j, k, p, q = 0; 

    // This loop runs T(n) time 

    for (i = 1; i < n; ++i) 
    { 
     p = 0; 

     // This loop runs T(Log Log n) time 
     for (j=n; j > 1; j=j/2) 
      ++p; 

     // This loop runs T(Log Log n) time 
     for (k=1; k < p; k=k*2) 
      ++q; 

    } 
    return q; 
} 

但時間如果循環變量被劃分/乘以常量，則循環的複雜度被視爲O（Logn）。

for (int i = 1; i <=n; i *= c) { 
    // some O(1) expressions 
} 

for (int i = n; i > 0; i /= c) { 
    // some O(1) expressions 
} 

但它提到，內環採取Θ（日誌日誌n）的每一次，任何人都可以解釋我AR的原因是答案錯了嗎？

Answer 1

這個問題是有難度的 - 有什麼之間的代碼運行是和什麼返回值是有區別的。

第一個循環的運行時確實是O（log n），而不是O（log log n）。我在這裏轉載的：

p = 0; 
for (j=n; j > 1; j=j/2) 
    ++p; 

在每次迭代中，j值下降的兩個因素。這意味着此循環終止所需的步驟數由k的最小值給出，以使得n/2 = 1。解決，我們看到k = 0（log n）。

請注意，此循環的每次迭代都會將p的值增加1。這意味着在循環結束時，p的值是Θ（log n）。因此，下一個循環的確在時間O（log log n）上運行：對於（k = 1; k < p; k = k * 2） ++ q; }

這樣做的原因是，當使用類似的推理，以前面的部分，該環路的運行時間是Θ數（log P），並且由於P = Θ（log n）的，這最終被Θ（日誌日誌n）。

但是，問題是而不是詢問運行時是什麼。這是問什麼返回值是。在每次迭代中，最終返回的q的值將增加Θ（log log n），因爲它在每次運行Θ（log log n）的循環的迭代中增加一次。這意味着q的淨值是Θ（n log log n）。因此，儘管算法在時間O（n log n）中運行，但其返回值爲O（n log log n）。

希望這會有所幫助！

Answer 2

答案是（D）O（n * log（log n））。原因如下： -

第一個for循環包含其他2個循環，分別基於j和k的值。此外，j從n減半，直到它大於1.所以，p將等於最大整數（log n）。並且，k倍增直到它等於p ---其中p已經從前一個循環中設置並且將等於[log n]，其中[x]等於x的最大整數。

因此，第三個循環將運行log（log n）時間，所以q的值將是log (log n)。因此，兩個內部循環都是外部for循環的一部分，運行n次。

近似值q = n * log（log n））= O（n log（log n））。

Answer 3

的唯一的事情錯了，我看到這裏涉及到第二個循環： 爲（J = N; J>時1;當J = J/2） 你說在註釋：這個循環運行Θ（日誌日誌n）的時間

在我看來，這個循環運行O（log n）的時間

運行時間爲第一和第三環是正確的（O（n）和O（日誌日誌N））。

編輯：我同意以前的答案。我沒有注意到問題是關於返回值，而不是運行時間！