Рубрики

ВОРОТА | GATE CS 2013 | Вопрос 31

Рассмотрим следующую функцию:

int unknown(int n) {

    int i, j, k = 0;

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

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

            k = k + n/2;

    return k;

 }

(A)

(B)

(C)

(D)

(А) А
(Б) Б
(С) С
(D) D

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

Здесь мы должны сказать, что значение k вернуло не сложность времени.

for (i  = n/2; i <= n; i++)
        for (j = 2; j <= n; j = j * 2)
            k = k + n/2;
    return k;

Внешний цикл работает н / 2 раза
Внутренний цикл выполняется logn раз. (2 ^ k = n => k = logn).
Теперь, смотря на значение k во внутреннем цикле, n добавляется к k, logn times, поскольку внутренний цикл работает logn times.
Следовательно, значение k после однократного запуска внутреннего цикла равно n * logn.
Поэтому общая сложность времени умножается на внутреннюю сложность цикла, которая (n для внешнего и nlogn для внутреннего) n ^ 2logn.

Смотрите http://geeksquiz.com/algorithms-analysis-of-algorithms-question-5/

Это решение предоставлено Parul Sharma.
Тест на этот вопрос

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

ВОРОТА | GATE CS 2013 | Вопрос 31

0.00 (0%) 0 votes