Рубрики

ВОРОТА | GATE-CS-2015 (набор 1) | Вопрос 65

Рассмотрим следующую функцию 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
(С) nlogn
(D) nlog (logn)

Ответ: (D)
Объяснение:

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

// Этот цикл выполняется Θ (n) раз
для (я = 1; я это
для (j = n; j> 1; j = j / 2)
++ р;

// Поскольку вышеуказанный цикл выполняется runs (Log n) раз, p = Θ (Log n)
// Этот цикл выполняется Θ (Log p) раз, когда loglogn
для (k = 1; k

T (n) = n (logn + loglogn)
T (n) = n (logn) доминантный

Но, пожалуйста, обратите внимание, что здесь мы возвращаем q, которое лежит в loglogn, поэтому ans должно быть T (n) = nloglogn

Обратитесь к этому для деталей.
Тест на этот вопрос

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

ВОРОТА | GATE-CS-2015 (набор 1) | Вопрос 65

0.00 (0%) 0 votes