Рубрики

Вопрос о сложности времени

Какова временная сложность следующей функции fun ()? Предположим, что log (x) возвращает значение журнала в базе 2.

void fun()

{

   int i, j;

   for (i=1; i<=n; i++)

      for (j=1; j<=log(i); j++)

         printf("GeeksforGeeks");

}

Сложность по времени указанной функции может быть записана как Θ (log 1) + Θ (log 2) + Θ (log 3) +. , , , + Θ (log n), что Θ (log n!)

Порядок роста 'log n!' и 'n log n' одинаково для больших значений n, т.е. Log (log n!) = Θ (n log n). Таким образом, временная сложность fun () равна Θ (n log n).

Выражение Θ (log n!) = Θ (n log n) можно легко вывести из следующего приближения Стирлинга (или формулы Стирлинга) .


      log n! = n log n - n + O(log(n)) 

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Источники:
http://en.wikipedia.org/wiki/Stirling%27s_approximation

Рекомендуемые посты:

Вопрос о сложности времени

0.00 (0%) 0 votes