Сложность Big-O -> нахождение суммы элемента массива для цели

Question

Вопрос касается проблемы кодирования летучей мыши. Определите, существует ли в массиве целых чисел группа чисел, суммирующая с целью.

Ниже приведены стандартные решения в * 1023. *

public boolean groupSum(int start, int[] nums, int target) {
  final int len = nums.length;

  if (start == len) {
    return target == 0;
  }

  if (groupSum(start + 1, nums, target - nums[start])) {
      return true;
  } 
  if (groupSum(start + 1, nums, target)) {
    return true;
  }
  return false;     
}

Похоже, что приведенный выше алгоритм можно разбить на рекурсивное решение:

T (n) = 2T (n - 1) + O (n⁰)

И с использованием вычитать и покорять сложность времени Big-O получается равной

O (2 ^ n) ? Это верно?

Имеет ли значение тот факт, что рекурсивный вызов в выражении if влияет на сложность?

Answer 1

Да, сложность O(2^N). На каждой позиции у вас есть два варианта:

1. Возьмите предмет.
2. Не берите предмет.

У вас есть 2 способа на каждый шаг, и у вас есть N решений, так что в общей сложности 2^N. Тот факт, что вы пишете это в условии if или нет, не имеет значения. Ускорение едва заметно.

PS: Это стандартная проблема суммы подмножеств , которая может быть решена за гораздо меньшее время

Answer 2

Короче говоря, вам нужно проверить (в худшем случае, который нам всем нравится) все перестановки ваших n элементов.

Так что не имеет значения, выполняется ли код в операторах if или иным образом, число комбинаций остается неизменным ...

Конечно, если вы используете эвристику и все виды других трюков, чтобы сократить (значимым образом) количество проверок, которые вам нужно сделать, что может изменить картину. Но в своем вопросе вы не обращаетесь ни к чему из этого.