Рубрики

Алгоритмы | Анализ алгоритмов (рецидивов) | Вопрос 3

Какова наихудшая временная сложность последующей реализации задачи о сумме подмножеств.

// Возвращает true, если есть подмножество set [] с солнцем, равным данной сумме

bool isSubsetSum(int set[], int n, int sum)

{

   // Базовые случаи

   if (sum == 0)

     return true;

   if (n == 0 && sum != 0)

     return false;

   

   // Если последний элемент больше суммы, тогда игнорируем его

   if (set[n-1] > sum)

     return isSubsetSum(set, n-1, sum);

   

   / * иначе, проверьте, можно ли получить сумму любым из следующих

      (а) включая последний элемент

      (б) исключая последний элемент * /

   return isSubsetSum(set, n-1, sum) || 

          isSubsetSum(set, n-1, sum-set[n-1]);

}

(A) O (n * 2 ^ n)
(B) O (n ^ 2)
(C) O (n ^ 2 * 2 ^ n)
(D) O (2 ^ n)

Ответ: (Д)
Объяснение: Ниже приведено повторение для данной реализации задачи суммы подмножеств

T (n) = 2T (n-1) + C1
Т (0) = С1

Где C1 и C2 — некоторые машинные константы.

Решение повторения O (2 ^ n)

Мы можем увидеть это с помощью метода дерева повторений

           C1
       /       \
    T(n-1)     T(n-1) 


                    C1
                /       \
              C1           C1
           /     \        /    \
      T(n-2)  T(n-2)   T(n-2)  T(n-2)

                    C1
                /       \
              C1           C1
           /     \        /    \
          C1     C1      C1     C1
        /   \   /  \    /  \   /  \

       
If we sum the above tree level by level, we get the following series
T(n) = C1 + 2C1 + 4C1 + 8C1 + ...
The above series is Geometrical progression and there will be n terms in it.
So T(n) = O(2^n)    

Тест на этот вопрос

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

Алгоритмы | Анализ алгоритмов (рецидивов) | Вопрос 3

0.00 (0%) 0 votes