время выполнения из программного кода

Question

Мне нужна твоя помощь.Не могли бы вы мне помочь, пожалуйста.

Ввод: Массив A с n натуральными числами.

count = 0
for each subset S of 4 elements of A do:
  sum = "sumFormula" from i = 0 to 3  S[i]
  for i from 0 to n-1 do:
        if sum == A[i]:
            count = count+1
return count.

Я не понял этого.Сколько времени это займет?

Моя идея: я думаю, что он имеет экспоненциальное время выполнения, потому что когда я удваиваю входной размер, он возводится в квадрат.Но я не уверен.

Answer 1

Большая часть сложности алгоритма скрыта.

В частности:

для каждого подмножества S из 4 элементов в A

Как определяются эти подмножества?
Существует 2 ^ n возможных подмножеств множества с n элементами.Просто этот первый шаг может быть причиной экспоненциального времени выполнения.

Оставшаяся часть алгоритма по существу вычисляет сумму каждого из этих подмножеств.Это не сильно повлияет на время выполнения.