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

Question

Мне трудно понять следующие утверждения из Алгоритмы С. Дасгупты, CH Пападимитриу и У. В. Вазирани - стр. 24 , что они представляют сумму O (n) в виде O (n ² ).Но мое понимание O (n) - это линейная функция от n, и она никогда не может быть квадратичной независимо от того, сколько раз линейные функции добавлены (для любого заданного n).Они дают объяснение, как показано ниже для примера 13 x 11 в двоичной записи.

        1 1 0 1
      x 1 0 1 1
      ----------
        1 1 0 1 (1101 times 1)
      1 1 0 1   (1101 times 1, shifted once)
    0 0 0 0     (1101 times 0, shifted twice)
+ 1 1 0 1       (1101 times 1, shifted thrice)
----------------
1 0 0 0 1 1 1 1 (binary 143)

Если x и y (здесь 1101 и 1011) оба n битов, то существует n промежуточныхстроки длиной до 2n бит (с учетом сдвига).Общее время, необходимое для сложения этих строк, делая два числа за раз, составляет O (n) + O (n) + ... + O (n), что составляет O (n ^{2 *).1013 *)} , квадратичный по размеру входов.

Извините, если это очевидно, но может кто-нибудь помочь мне понять, почему это O (n ² )

Answer 1

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

Answer 2

Если вы делаете что-то, что займет N секунд, и повторите это N раз. Сколько секунд потребуется, чтобы закончить?

N = 2 => 2*2 seconds.
N = 3 => 3*3 seconds.
N = 4 => 4*4 seconds.

      => N^2 seconds.

Answer 3

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

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

n*n is O(n^2)

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

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

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

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

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

Answer 4

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

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

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

Answer 5

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

Answer 6

Основная идея: потому что постоянный коэффициент, скрытый в 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

Answer 7

Многие ответы здесь забыли о важном предположении. Если у вас есть 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 <sup>2 = O (n ² ).

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

Answer 8

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

Answer 9

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

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

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

Answer 10

Вы должны добавить два числа n-размера (за O (n) раз), n раз.n (O (n)) = O (n * n) = O (n ^ 2).