Наши профи и различные материалы говорят суммирование (n) = (n) (n + 1)/2 и, следовательно, является тета (n^2). Но интуитивно, нам просто нужен один цикл, чтобы найти сумму первых n членов! Итак, это должна быть тета (n). Интересно, что мне здесь не хватает ?!Как суммирование (n) Theta (n^2) по его формуле, но Theta (n) ij мы просто рассматриваем его как единую для цикла?
Все эти ответы являются непониманием проблемы, как и исходный вопрос: точка не в измерении сложности выполнения алгоритма для суммирования целых чисел, это говорит о том, как рассуждать о сложности алгоритма, который принимает i шагов за каждый проход для i в 1..n. Рассмотрим сортировку вставки: на каждом шаге i для вставки одного элемента в исходный список список результатов составляет i элементов длиной, поэтому для выполнения вставки требуется i шагов (в среднем). Какова сложность сортировки вставки? Это сумма всех этих шагов или сумма i за i в 1..n. Эта сумма равна n(n+1)/2, которая имеет в ней n^2, поэтому сортировка вставки - это O (n^2).
+1, но я не пропустил это в своем ответе – Paulpro
Хронометраж из этого кода Θ(1) (при условии, сложение/вычитание и multiplaction постоянные операции времени):
result = n*(n + 1)/2 // This statement executes once
Хронометраж следующий псевдокод, который является то, что вы описали, является действительно Θ(n) :
result = 0
for i from 1 up to n:
result = result + i // This statement executes exactly n times
Вот еще один способ его вычисления, который имеет время работы Θ(n²):
result = 0
for i from 1 up to n:
for j from i up to n:
result = result + 1 // This statement executes exactly n*(n + 1)/2 times
Все три из этих кодовых блоков вычисляют сумму натуральных чисел от 1 до n.
Этот цикл Θ(n²), вероятно, является типом, который вас просят проанализировать. Всякий раз, когда у вас есть цикл вида:
for i from 1 up to n:
for j from i up to n:
// Some statements that run in constant time
У вас есть ход времени сложность Θ(n²), потому что эти действия выполняются точно summation(n) раз.
Хорошо, я думаю, я понимаю здесь.Итак, суммирование (n) на самом деле является тета (n), не так ли ?! Потому что формула просто дает окончательный результат, и здесь это несущественно. –
@AnoopDixith Время вычисления 'Summation (n)' изменяется в зависимости от того, как это делается, и может быть выполнено в 'Θ (1)' с помощью закрытого форума. Математическая функция 'Summation' сама есть' Θ (n²) ', потому что ее выход растет пропорционально' n²'. – Paulpro
Суммирование (n), являющееся n (n + 1)/2, относится к сумме чисел от 1 до n. Это математическая формула и может быть рассчитана без цикла, который является O (1) раз. Если вы перебираете массив, чтобы суммировать все значения, которые являются алгоритмом O (n).
Я думаю, проблема в том, что вы ошибочно полагаете, что формула суммирования имеет временную сложность theta (n^2).
Формула имеет n^2 в ней, но для нее не требуется количество вычислений или количество времени, пропорциональное n^2.
Подведение итогов до n в цикле было бы тета (n), как вы говорите, потому что вам нужно будет проходить через цикл n раз.
Однако вычисление результата уравнения n (n + 1)/2 будет просто тета (1), так как это единственный расчет, который выполняется один раз независимо от того, насколько велика n.
http://stackoverflow.com/questions/1377282/can-someone-explain-how-big-oh-works-with-summations –