Big O, в чем сложность суммирования ряда из n чисел?

Ответ 1

большая нотация O > может использоваться для определения скорости роста любой функции.

В этом случае, похоже, книга не говорит о временной сложности вычисления значения, а о самом значении. И n(n+1)/2 - O(n^2).

Ответ 2

Вы смешиваете сложность времени выполнения и размер (сложность) результата.

Время выполнения суммирования, одно за другим, первые n последовательных чисел действительно O (n). ¹

Но сложность результата, т.е. размер "суммы от 1 до n" = n ( n - 1)/2, равен O ( n ^ 2).

¹ Но для сколь угодно больших чисел это упрощается, так как добавление больших чисел занимает больше времени, чем добавление небольших чисел. Для точного анализа времени выполнения вам действительно нужно рассмотреть размер результата. Однако это обычно не имеет отношения к программированию, даже даже в чисто теоретической информатике. В обоих доменах суммирующие числа обычно считаются операцией O (1), если явно не требуется иное доменом (т.е. При реализации операции для библиотеки bignum).

Ответ 3

n (n + 1)/2 - быстрый способ суммирования последовательной последовательности из N целых чисел (начиная с 1). Я думаю, вы вводите в заблуждение алгоритм с большими обозначениями!

Если вы думали об этом как о функции, то большая сложность этой функции - O (1):

public int sum_of_first_n_integers(int n) {
  return (n * (n+1))/2;
}

Наивная реализация имела бы большую сложность O (n).

public int sum_of_first_n_integers(int n) {
  int sum = 0;
  for (int i = 1; i <= n; i++) {
    sum += n;
  }
  return sum;
}

Даже если посмотреть на каждую ячейку одной n-на-n-матрицы, будет O (n ^ 2), так как матрица имеет n ^ 2 ячейки.

Ответ 4

Итак, я предполагаю, что это на самом деле ссылка на Cracking the Coding Interview, которая содержит этот абзац в реализации StringBuffer:

При каждой конкатенации создается новая копия строки, а две строки копируются по символу. Первый итерация требует, чтобы мы скопировали символы x. Вторая итерация требуется копировать символы 2x. Третья итерация требует 3x, и скоро. Таким образом, общее время O(x + 2x + ... + nx). Это уменьшает до O(xn²). (Почему это не O(xnⁿ)? Потому что 1 + 2 + ... n равно n(n+1)/2или, O(n²).)

По какой-то причине я нашел это немного запутанным в моем первом прочтении. Важным признаком является то, что n умножает n, или, другими словами, что n² происходит, и это доминирует. Вот почему в конечном итоге O(xn²) является просто O(n²) - x является своего рода красной селедкой.

Ответ 5

На самом деле проблема не сложна, а сложность алгоритма.

В вашем случае, если вы решите перебирать все числа, сложность, действительно, O(n).

Но это не самый эффективный алгоритм. Более эффективным является применение формулы - n*(n+1)/2, которая является постоянной, и, следовательно, сложность O(1).

Ответ 6

У вас есть формула, которая не зависит от количества добавляемых чисел, поэтому это алгоритм с постоянным временем или O (1).

Если вы добавляете каждое число по одному за раз, то это действительно O (n). Формула является ярлыком; это другой, более эффективный алгоритм. Ярлык работает, когда добавляемые числа - все 1..n. Если у вас есть несмежная последовательность чисел, то формула ярлыка не работает, и вам придется вернуться к алгоритму "один за другим".

Однако это не относится к матрице чисел. Чтобы добавить две матрицы, все равно O (n ^ 2), потому что вы добавляете n ^ 2 различных пар чисел, чтобы получить матрицу из результатов n ^ 2.

Ответ 7

Существует разница между суммированием N произвольных целых чисел и суммированием N, которые все в строке. Для 1 + 2 + 3 + 4 +... + N вы можете воспользоваться тем фактом, что их можно разделить на пары с общей суммой, например. 1 + N = 2+ (N-1) = 3+ (N-2) =... = N + 1. Итак, N + 1, N/2 раза. (Если есть нечетное число, один из них будет непарным, но с небольшим усилием вы можете увидеть, что в этом случае выполняется одна и та же формула.)

Это не O (N ^ 2). Это просто формула, которая использует N ^ 2, фактически O (1). O (N ^ 2) означало бы (примерно), что количество шагов для его вычисления растет, как N ^ 2, при больших N. В этом случае количество шагов одинаково, независимо от N.

Ответ 8

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

 int sum = 0;
     for (int i = 1; i <= n; i++) {
     sum += n;
   }
 return sum;

он аналогичен 1 + 2 + 3 + 4 +...... + n. в этом случае сложность алгоритма вычисляется как количество операций сложения, которое является O (n).

Второй способ нахождения ответа на сумму рядов n натурального числа - это direst-формула n * (n + 1)/2. эта формула использует умножение вместо повторного добавления. операция умножения не имеет линейной временной сложности. существуют различные алгоритмы, доступные для умножения, которые имеют временную сложность от O (N ^ 1.45) до O (N ^ 2). поэтому в случае умножения временная сложность зависит от архитектуры процессора. но для целей анализа временная сложность умножения рассматривается как O (N ^ 2). поэтому, когда вы используете второй способ найти сумму, тогда сложность времени будет O (N ^ 2).

здесь операция умножения не такая же, как операция сложения. если кто-либо знает об объекте компьютерной организации, тогда он может легко понять внутреннюю работу операции умножения и дополнения. схема умножения более сложна, чем схема сумматора, и для вычисления результата требуется гораздо больше времени, чем схема сумматора. поэтому временная сложность суммы рядов не может быть постоянной.