Big-Oh: Как O (n) + O (n) +… + O (n) могут быть равны на O (n ^ 2)?

Если есть n операций со сложностью O ( n ), тогда общая сложность составляет n · O ( n ), что составляет O ( n ² ).

То, что является O (n), не является O (n ² ) **, если оно умножено на коэффициент константы .

n is O(n)  
7n is O(n)  
100000n is O(n)

n*n is O(n^2)

Вот формальное определение big-O, процитированное из Википедии:

Пусть f (x) и g (x) - две функции. определены на некотором подмножестве реальных числа.

пишут тогда и только тогда, когда для достаточно больших значений x, f (x) не более постоянная, умноженная на g (x) в абсолютная величина. То есть f (x) = O (g (x)) тогда и только тогда, когда существует положительное действительное число M и действительное число x ₀ такое, что

** ПРЕДУПРЕЖДЕНИЕ: Big O - это верхняя граница. Все, что является O (n), технически также является O (n ² ). См. Различия между Большой Тетой и Большой Омегой.

http://en.wikipedia.org/wiki/Big_O_notation

Когда вы говорите «любое данное n», вы забываете, что когда «данное n» равно n само , тогда вы выполняете O (n ) операция n раз. Это n ² .

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

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

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

A O (n) операция выполнена n раз будет O (n ^ 2) . Более строго, если количество операций O (n) линейно зависит от размера ввода, n , то у вас будет случай O (n ^ 2) .

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

Один из недостатков нотации Big-O заключается в том, что она способствует неправильным представлениям, например, о предмете вашего вопроса. O (n) + O (n) предполагает, что вы добавляете к себе класс линейных функций, но на самом деле это означает «класс суммы любых двух линейных функций». Сумма снова линейна, что приятно, но этот результат зависит от наличия только двух (или любого постоянного числа) суммированных линейных функций.

Итак, в контексте, ваш вопрос на самом деле означает «почему сумма увеличивающегося числа линейных функций также не является линейной?». Набросок доказательства довольно прост:

'
- Assume, for simplicity, that all linear functions are of the form f(n) = c*n, c >= 1
- Suppose we have an increasing-as-N-increases set of summed linear functions
- Assume the sum of that set of functions is linear, ie. of the form c*n
  - Try to find a value of c that works for all values of N
  - But, for any c that works for N=x, it will fail for N=x+1 because there is another addition
  - Contradiction
- The sum of the set of functions is not linear

Нужно сложить два числа размера n (что занимает время O(n)), n раз. n(O(n)) = O(n*n) = O(n^2).

Ответ очень прост:

O (n) + O (n ) + ・ ・ ・ + O (п) = X (n)

Если X постоянен и не изменяется при вводе, то он все еще остается O (n).

Многие ответы здесь забыли о важном предположении. Если у вас есть n операций, каждая из которых равна O (n), из этого не автоматически следует, что сумма равна O (n ² )! Скажем, k-я операция занимает k * n раз (поэтому она постоянно умножается на n) - первая операция занимает n раз, вторая 2 * n и т. Д. Тогда сумма первых n операций равна O (n ³ ) .

Для неверующих, вот пример такого злоупотребления из CLRS:

Ложное утверждение:

 n
 Σ  k = O(n)
i=1

Доказательство по индукции:

Для n = 1, 1 = O (1).

Для n + 1, предполагая, что гипотеза верна для n,

n+1       n
 Σ  k = ( Σ k) + (n+1) =  O(n) + n = O(n)
i=1      i=1

«Доказательство» неверно, сумма равна O (n ² ).

Вы можете сказать, что O (n) + ... + O (n) равно O (n ² ), если все константы, скрытые в большом O , ограничены некоторой константой . В этом случае вы можете написать

O (n) + ... + O (n) <= kn + kn + ... + kn <= kn ² = O ( n ² ).

Если константы не ограничены, это неправильно.