以下代碼片段的時間複雜度是多少？

-6

以下代碼片段的時間複雜度是多少？我們有3個嵌套循環。以下代碼片段的時間複雜度是多少？

void function(int n) 
{ 
int i, j,k, count 0; 

for (i= n/3; i <= n; i++) 

    for (j =1; j <= n/2; j= 2 *j) 

     for (k= 1; k*k<= n; k++) 

      count ++; 
}

來源

2014-01-28 learner

嘗試用正的樣本值運行，則啓動在50步上升，然後繪製結果agiast該函數結束時的計數值。使用Excel進行繪圖，只輸出n，用分隔它們的標籤進行計數，每個標籤都在一個新行上運行，然後可以將+ paist複製到excel中。 –

你應該自己做功課。讀我的答案不會教你什麼。

第一循環： O（N * 2/3）
第二循環：O（LOG2（N/2））
第三循環： O（SQRT（n））的

總：O型（N * 2/3 *的log 2（N/2）* SQRT（n））的

證明：

<?php 
function x ($n) 
{ 
    $count=0; 

    for ($i= $n/3; $i <= $n; $i++) 
     for ($j =1; $j <= $n/2; $j= 2 *$j) 
      for ($k= 1; $k*$k<= $n; $k++) 
       $count ++; 
    return $count; 
} 

$base = 10; 
for ($i = 0 ; $i != 4 ; $i++) 
{ 
    $x = x($base); 
    $y = 2*$base/3 * log($base/2,2) * sqrt($base); 
    $ratio = $x/$y; 
    printf ("%-4d $ratio<br>", $base); 
    $base *= 10; 
} 
?>

輸出：

10 1.2870133211442 
    100 1.0684184354174 
1000 0.9845391957853 
10000 1.0580203701412

來源

2014-01-28 19:43:53

形式上（Sigma公司符號）和根據經驗，這是您的算法精確解：

enter image description here

來源

2014-06-27 04:35:21

以下代碼片段的時間複雜度是多少？

回答

相關問題