Алгоритм Практика Вопрос для начинающих | Комплект 1

01.01.2020Анализ

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

unsigned fun(unsigned n)
{

if (n == 0) return 1;

if (n == 1) return 2;

return fun(n-1) + fun(n-1);

}

Рассмотрим следующие вопросы для кода выше, игнорируя оптимизацию компилятора.
а) Что делает приведенный выше код?
б) Какова временная сложность вышеуказанного кода?
в) Можно ли уменьшить временную сложность вышеуказанной функции?

Что делает fun (n)?
В приведенном выше коде fun (n) равно 2 * fun (n-1). Таким образом, вышеприведенная функция возвращает 2 ⁿ . Например, для n = 3 он возвращает 8, для n = 4 он возвращает 16.

Какова временная сложность веселья (n)?
Временная сложность вышеуказанной функции экспоненциальная. Пусть сложность Времени будет T (n). T (n) можно записать следующим образом. Здесь C — машинно-зависимая константа.

T(n) = T(n-1) + T(n-1) + C
     = 2T(n-1) + C

Указанная рекуррентность имеет решение как Θ (2 ⁿ ). Мы можем решить это методом рекуррентного дерева. Дерево повторения будет двоичным деревом с высотой n, и каждый уровень будет полностью заполнен, за исключением, возможно, последнего уровня.

                       C
                  /        \
               C              C
            /     \         /     \
          C        C       C        C  
         / \      / \     / \      / \
        .  .     .   .   .   .    .   .
        .  .     .   .   .   .    .   .
       Height of Tree is Θ(n)

Можно ли уменьшить временную сложность веселья (n)?
Простой способ уменьшить сложность времени — сделать один звонок вместо двух.

unsigned fun(unsigned n)
{

if (n == 0) return 1;

if (n == 1) return 2;

return 2*fun(n-1);

}

Временная сложность приведенного решения равна Θ (n). T Пусть сложность Времени будет T (n). T (n) можно записать следующим образом. Здесь C — машинно-зависимая константа.

T(n) = T(n-1) + C

Мы можем решить это методом рекуррентного дерева. Дерево рекуррентности будет перекошенным двоичным деревом (у каждого внутреннего узла есть только один дочерний элемент) с высотой n.

            C
           /
          C
         /
        C
       /
      .  
    .
 Height of Tree is Θ(n)

Вышеприведенная функция может быть дополнительно оптимизирована с использованием метода «разделяй и властвуй» для расчета мощностей.

unsigned fun(unsigned n)
{

if (n == 0) return 1;

if (n == 1) return 2;

unsigned x = fun(n/2);

return (n%2)? 2*x*x: x*x;

}

Временная сложность приведенного решения is (Logn). Пусть сложность Времени будет T (n). T (n) можно приблизительно записать в виде следующего повторения. Здесь C — машинно-зависимая константа.

T(n) = T(n/2) + C

            C       
           /
          C
         /
        C
       /
      .  
    .
 Height of Tree is Θ(Logn)

Мы также можем напрямую вычислять fun (n), используя битовый оператор сдвига влево '

unsigned fun(unsigned n)
{

return 1 << n;

}

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

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

Алгоритм Практика Вопрос для начинающих | Комплект 1

0.00 (0%) 0 votes