Какова временная сложность следующего фрагмента кода?

-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 значение count в конце функции. Используйте excel для выполнения графика, просто выведите n, подсчитайте с помощью закладки, разделяющей их, каждый из которых запускается на новой строке, тогда вы можете скопировать + paist в excel. –

Вы должны сделать домашнее задание самостоятельно. Чтение моего ответа ничего не научит вас.

1-й цикл: О (п * 2/3)
2-й цикл: O (log2 (п/2))
третьего цикла: O (SQRT (п))

всего: O (п * 2/3 * log2 (п/2) * SQRT (п))

Доказательство:

<?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

Какова временная сложность следующего фрагмента кода?

ответ

Смежные вопросы