Сложность времени подсчета сумм.

Question

Обычно при работе с комбинациями сложность Big-O выглядит O (n выбирает k). В этом алгоритме, я генерация всех комбинаций в пределах массива, которые соответствуют целевой сумме:

def combos(candidates,start, target): 
    if target == 0: 
     return [[]] 
    res = [] 
    for i in range(start,len(candidates)): 
     for c in combos(candidates, i+1, target-candidates[i]): 
      res.append([candidates[i]]+ c) 
    return res 


print combos([2,1,10,5,6,4], 10) 
# [[1, 5, 4], [10], [6, 4]] 

Я с трудом определяющей Big-O здесь, это O(n choose t) алгоритма? Если нет, что это такое и почему?

Answer 1

Если точка, чтобы дать наихудшего литой сложности с точки зрения заданного размера, п, то это Θ (2 ^п). Для любого набора, если целевая сумма достаточно велика, вы в конечном итоге перечисляете все возможные подмножества набора. Это Θ (2 ^п), как можно видеть двумя способами:

• Каждый элемент может быть выбран или нет.

• Это ваш Θ (п выбрать к), просто суммируются по всем К.

---

Более утонченная оценка будет учитывать как п и целевой сумму т. В этом случае, следуя рассуждениям 2-го пункта выше, тогда, если все элементы (и целевая сумма) являются целыми положительными числами, тогда сложность будет равна Θ (n выберите k) для k подведение итогов до t.

Answer 2

Ваш алгоритм не менее O(2^n), и я считаю, что это O(n * 2^n). Вот объяснение.

В вашем алгоритме вы должны сгенерировать все возможные комбинации набора (за исключением пустого набора). Так что это:

O(2^n) по крайней мере. Теперь для каждой комбинации вы должны подвести итог. Некоторые наборы имеют длину 1 на длину n, но большинство из них было бы где-то длиной n/2. Поэтому я считаю, что ваша сложность близка к O(n * 2^n).