Большой О, какова сложность суммирования серии из n чисел?

Question

Я всегда думал о сложности:

1 + 2 + 3 + ... + n - это O (n), а сумма двух n по n матриц будет равна O (n ^ 2).

Но сегодня я прочитал из учебника: «по формуле для суммы первых n целых чисел это n (n + 1) / 2», а затем так: (1/2) n ^ 2 + (1 / 2) n и, следовательно, O (n ^ 2).

Что мне здесь не хватает?

Answer 1

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

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

Answer 2

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

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

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

---

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

Answer 3

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

Если вы думаете о ней как о функции, то сложность этой функции big-oh равна 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 ячеек.

Answer 4

Так что я предполагаю, что это на самом деле ссылка на Взлом интервью Coding , в котором этот абзац описан в реализации 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 - это своего рода красная сельдь.

Answer 5

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

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

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

Answer 6

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

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

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

Answer 7

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

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

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

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

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

Answer 8

Существует разница между суммированием 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.