Как мне добраться до финального выражения в T(n)

Question

Я читал об алгоритмической сложности, и я понимаю, как добраться до формулы ниже:

но не похоже, что вы получите эту формулу после очистки суммы:

Разве это внутренние члены суммы могут быть нарисованы снаружи, а внутри было бы что-то вроде бесконечного ряда (n*(n + 1))/2 .. но не как операции повышения, у меня есть сомнения?

С уважением Cronos

Answer 1

Прежде чем ответить, я должен отметить две вещи.

• Во-первых, сумма не соответствует тому, что вы предлагаете. Возможно, вы неправильно поняли? Или сделал ошибку при копировании эксперимента?
• И во-вторых, пожалуйста, предоставьте некоторую предысторию, например, алгоритм, анализ которого дал выражение для T(n), так что вопрос будет как минимум косвенно актуален для сообщества.

Во-первых, давайте упростим выражение для T(n), чтобы мы имели

T(n) = 3 + 3 + 3n + 7 * sum_{i=1}^{n-1} (n-i).

Заметив, что сумма n-i за i=1,2,...,n-1 эквивалентно сумме 1+2+...+n-iкоторый, как мы помним из средней школы, оценивает n(n-1)/2Мы получаем новое выражение для T(n):

T(n) = 3 + 3 + 3n + 7 * n*(n-1)/2
     = 6 + 3n + 7n(n-1)/2
     = 7n^2/2 - 7n/2 + 6n/2 + 6
     = 7^n2/2 - n/2 + 6