Почему большая сложность этого алгоритма O(n^2)?

Я знаю, что большая сложность этого алгоритма O(n^2), но я не могу понять, почему.

int sum = 0; 
int i = 1; j = n * n; 
while (i++ < j--) 
  sum++;

даже если мы ставим j = n * n в начале мы увеличиваем i и уменьшаем j во время каждой итерации, поэтому результирующее число итераций не должно быть намного меньше n*n?

7 53
algorithm time-complexity big-o complexity-theory asymptotic-complexity

7 ответов:

во время каждой итерации вы увеличиваете i и декремента j что эквивалентно просто инкрементируя i на 2. Поэтому общее число итераций равно n^2 / 2, и это все еще O(n^2).

113

сложность big-O игнорирует коэффициенты. Например: O(n),O(2n) и O(1000n) все же O(n) бег времени. Аналогично,O(n^2) и O(0.5n^2) как O(n^2) бег времени.

в вашей ситуации вы по существу увеличиваете свой счетчик циклов на 2 каждый раз через свой цикл (так как j-- аналогично i++). Так что ваше время выполнения O(0.5n^2), но это то же самое, что O(n^2) при удалении коэффициент.

52

у вас будет точно n*n/2 итераций цикла (или (n*n-1)/2 если n странно). В биг-О'нотации у нас есть O((n*n-1)/2) = O(n*n/2) = O(n*n) потому что постоянные факторы "не учитываются".

11

Ваш алгоритм эквивалентен 

while (i += 2 < n*n) 
  ...

что это O(n^2/2) что же O(n^2) потому что большая сложность O не заботится о константах.

10

пусть m-количество итераций. Тогда,

i+m = n^2-m

Что дает,

m = (n^2-i)/2

в нотации Big-O это подразумевает сложность O(n^2).

4

Да, этот алгоритм O (n^2).

чтобы вычислить сложность, у нас есть таблица сложности:

O(1) O (log n) O(n) O (n log n)
O(n2) O (n^a) O (a^n) О (н!)

каждая строка представляет собой набор алгоритмов. Набор алгоритмов, который находится в O(1), тоже находится в O(n) и O (N^2) и т. д. Но не наоборот. Итак, ваш алгоритм реализует n * n/2 предложений.

O(n)

Итак, набор алгоритмов, которые включите сложность вашего алгоритма, это O(n2), потому что O(n) и O (nlogn) меньше.

например: До n = 100, сумма = 5000. => 100 o С(Н)

извините за мой английский.

4

несмотря на то, что мы устанавливаем j = n * n в начале, мы увеличиваем i и уменьшаем j во время каждой итерации, поэтому не должно ли полученное число итераций быть намного меньше n*n?

да! Вот почему это O (n^2). По той же логике, это много меньше n * n * n, Что делает его O (n^3). Это даже O (6^n), по аналогичной логике.

big-O дает вам информацию о верхних границах.

Я считаю, что вы пытаетесь спросить, почему сложность - это тета (n) или омега(n), но если вы просто пытаетесь понять, что такое big-O, вы действительно нужно понимать, что она дает верхние границы на функции в первую очередь.

0