Как найти временную сложность алгоритма ряда?

Question

Как я могу найти сложность следующего алгоритма, который дает суммирование ряда.

серии: 1+ (1 + 2) + (1 + 2 + 3) + ....... + (1 + 2 + 3 + ... + п)

алгоритм:

for(i=1; i<=n; i++){ 
     for(j=1; j<=i; j++){ 
      sum = sum + j; 
     } 
} 

Answer 1

Чтобы найти временной сложности, давайте проанализируем, сколько раз запустить ядро ​​(внутри петли).

Наружный цикл выполняется n раз, поэтому сложность не менее O (n).

Внутренний цикл выполняется

• один раз, когда я = 1
• дважды при I = 2
• ... N раз, когда я = п

Таким образом, общее число раз он будет выполняться - это сумма целых чисел между 1 и n: (n * (n + 1))/2 = n^2/2 + n/2, которая равна O (n^2).

Сложная сложность с другой стороны в этом случае проще. Поскольку требования к памяти не зависят от входной длины, сложность пространства вышеописанного алгоритма равна O (1) (что означает, что объем необходимой памяти одинаковый (в основном размер sum) независимо от n, и погодный результат помещается в sum).

Обратите внимание, что для одной и той же задачи разные алгоритмы могут иметь разные сложности. Как правильно заметил @AxelKemper в своем комментарии, вы можете выразить решение как один многочлен от n, поэтому наиболее эффективное решение будет иметь сложность O (1). Однако алгоритм выше не работает таким образом и имеет более высокую сложность.

Answer 2

Сумма

1+ (1 + 2) + (1 + 2 + 3) + ....... + (1 + 2 + 3 + ... + п)

равно

1/2 (1 + 1) + 2/2 (2 + 1) + 3/2 (3 + 1) + ....... + п/2 (n + 1)

Это можно переписать как

1/2 (1 + 2 + ... + n) + 1/2 (1 + 4 + 9 + ....+ П * п)

Это, в свою очередь, приводит к

п/4 (п + 1) + 1/12 (2n^3 + 3n^2 + п)

, который может быть упрощено до

п^3/6 + п^2/2 + п/3

Игнорируя длину слова n, сложность вычисления этого полинома не зависит от n.

Таким образом, временная сложность проблемы заключается в O(1)

Временной сложности алгоритма, показанном на это O(n^2) как объяснена в принятом ответе.