Какова временная сложность 4-х вложенных циклов, каждый из которых зависит от родительского цикла

Question

Я готовлюсь к техническому собеседованию, и у меня проблема с вычислением временной сложности моего алгоритма. Я знаю, что сложность времени для двух вложенных друг в друга циклов равна O (n ^ 2), но что, если вложенный l oop продолжает родительский элемент l oop. Примерно так:

for i in range(n):
  for j in range(i+1,n):
    for k in range(j+1,n):
      for q in range(k+1,n):
        print("Hello")

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

Буду признателен, если вы объясните свое решение.

Вот программа, которую я написал для подсчета количества операций:

def count_operations(n):
    number_of_operations = 1
    for i in range(n):
        number_of_operations += 1
        for j in range(i + 1, n):
            number_of_operations += 1
            for k in range(j + 1, n):
                number_of_operations += 1
                for q in range(k + 1, n):
                    number_of_operations += 1
    print(number_of_operations)


count_operations(1)
count_operations(2)
count_operations(3)
count_operations(4)
count_operations(5)
count_operations(6)
count_operations(7)
count_operations(8)

output

n: 1 , number of operations: 2
n: 2 , number of operations: 4
n: 3 , number of operations: 8
n: 4 , number of operations: 16
n: 5 , number of operations: 31
n: 6 , number of operations: 57
n: 7 , number of operations: 99
n: 8 , number of operations: 163

Answer 1

Ваши вложенные циклы повторяются по всем комбинациям из четырех чисел в range(n). Количество таких комбинаций задается формулой для биномиального коэффициента n выберите 4 , что:

n выберите 4 = n * (n -1) * (n-2) * (n-3) / (1 * 2 * 3 * 4)

Эта функция явно в O (n ⁴ ) поэтому самый внутренний l oop повторяется столько раз.

В общем, если вы вкладываете k циклов в один и тот же шаблон, то число итераций внутреннего l oop равно n. k , который находится в O (n ^k ), когда k является фиксированным числом.

Answer 2

Подумайте об этом так, есть n x (n-1) x (n-2) x (n-3) различные исполнения внутреннего содержимого l oop (что, вероятно, то, что вы должны считать, а не каждый уровень вложенных циклов) , Это работает следующим образом (но см. Комментарий ниже относительно фактического количества):

  n(n - 1)  x (n - 2)(n - 3)
= (n^2 - n) x (n^2 - 5n + 6)           # Expand each partial product.
= n^4 - 5n^3 + 6n^2 - n^3 + 5n^2 - 6n  # Expand final product.
= n^4 - 6n^3 + 11n^2 - 6n              # Combine like terms.

Счет фактический фактически является постоянным делителем этого (4! = 24), но это не имеет никакого отношения по сложности. Так как анализ сложности игнорирует постоянные коэффициенты и все, кроме наибольшего влияния, это, следовательно, эффективно O(n<sup>4</sup>).

---

Хорошее эмпирическое правило (для вещей, которые основаны на степени) - сводить в таблицу результаты и отрабатывать различия на каждом уровне увеличения полномочий. Когда увеличение становится постоянным, это сила, которую вы должны использовать. Формула f(n) = n(n-1)(n-2)(n-3) создает следующую таблицу (я добавляю различия каждого уровня):

    |        | DiffPrev at power level
 n  | f(n)   |     1 |    2 |   3 |  4
----+--------+-------+------+-----+----
 10 |   5040 |       |      |     |
 11 |   7920 |  2880 |      |     |
 12 |  11880 |  3960 | 1080 |     |
 13 |  17160 |  5280 | 1320 | 240 |
 14 |  24024 |  6864 | 1584 | 264 | 24
 15 |  32760 |  8736 | 1872 | 288 | 24
 16 |  43680 | 10920 | 2184 | 312 | 24
 17 |  57120 | 13440 | 2520 | 336 | 24
 18 |  73440 | 16320 | 2880 | 360 | 24
 19 |  93024 | 19584 | 3264 | 384 | 24
 20 | 116280 | 23256 | 3672 | 408 | 24

Поскольку она становится постоянной на уровне мощности 4, это индекс, который следует использовать.

Answer 3

Должно быть:

 O(n^4)

Таким образом, временная сложность вложенных циклов равна числу случаев, когда самый внутренний оператор выполняется в этом случае: 4