以下代码片段的时间复杂度是多少？

-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

以下代码片段的时间复杂度是多少？

回答

相关问题