Путаница со сложностью пузырьковой сортировки

Теперь уравнение (n*(n + 1))/2 = O(n^2) противоречиво.

Нет, это не так.

Потому что это не совсем уравнение.

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

предел ( n -> бесконечность ) f(n) ‹= C * n^2 ... для некоторой константы C.

^{(Есть более точные способы выразить это...)}

Интуитивно f(n) является членом множества O(n^2), что говорит нам о том, что f(n) растет пропорционально n^2 по мере того, как n становится действительно большим.

Легко доказать, что f(n) = (n*(n + 1))/2 принадлежит множеству O(n^2).

Неформально, когда n становится действительно большим для этого f(n), доминирует (n^2)/2 член уравнения, а n/2 становится незначительным.

Из википедии:

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

Итак, в вашем примере есть такая константа: если взять M = 3, то для всех n>0 сохраняется неравенство (n*(n + 1))/2 < 3*(n^2).

Более того, это определение говорит еще и о том, что: O(n^2) = O(n^2/180) = O(n^2 + n) и так далее.

Способ работы временной сложности заключается в том, что вы хотите найти, как функция ведет себя при очень больших значениях. Значение, которое вы замените N, не будет точным, но оно будет приблизительным для больших значений. Например, если N = 1 000 000 и ваша временная сложность равна O(n+1), отличаются ли 1 000 000 и 1 000 001?

Идея состоит в том, что вы сохраняете член из добавляемых, который асимптотически растет быстрее всего. Таким образом, в n*(n+1)/2 вы бы оставили n^2, так как он растет быстрее всего.

Если быть точным, O(...) — это набор функций, а не число. Иногда некоторые ребята ленятся и пишут x = O(y) вместо x \in O(y).

Вы можете найти точное определение множества O(y) в столбце формальное определение из этой таблицы: https://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann.E2.80.93Ландау_нотации

Что это значит неофициально? O(f(x)) содержит функции, которые растут примерно с одинаковой скоростью.
Например, если у вас есть g(x) = n^2 + 5n - 7000, то он находится в O(n^2), так как n^2 является доминирующей частью функции (сравните с точными определениями) .

Кроме того, постоянные факторы могут быть удалены. Итак, g(x) = 1000n^2 тоже есть в O(n^2).

Таким образом, O(...) всего лишь показатель того, от каких переменных и в какой степени что-то зависит. Например, существует вход (он может быть очень большим), где функция n^2 больше, чем 100000000 * n.

Из-за этого алгоритм со временной сложностью O(n^2) в целом не так хорош, как O(n). Но, что очень важно, на практике это может быть предпочтительнее, так как скрытые вещи во втором алгоритме могут быть настолько большими, что первый алгоритм лучше подходит для размеров входных данных, которые встречаются на практике. Однако существует ограничение на размер входных данных (оно может быть очень большим), при котором второй алгоритм будет улучшаться, но на практике они могут не встречаться.

O-обозначение предназначено для того, чтобы показать, как требуемое время растет с увеличением количества входных данных, поскольку количество входных данных становится большим. Например, предположим, что бит кода равен O(n). Если бы мы удвоили ввод, мы ожидали бы, что время выполнения (примерно) удвоится. Если мы утроим его, мы ожидаем, что время выполнения также утроится. Обратите внимание, что это будет верно независимо от любого фактора, который может существовать в гипотетической точной формуле для времени выполнения кода.

То же самое можно сказать и об O(n^2): удвоение приведет к учетверению и т. д. и т. д.

So :

O(n^2) == O(1/2*n^2) == O(2*n^2) == 0(1000000000*n^2)

Вот хорошее руководство.

Сложность любого алгоритма сортировки зависит от сравнений. В пузырьковой сортировке мы видели, что всего N-1 проходов. На первом проходе выполняется N-1 сравнений, чтобы поместить самый высокий элемент в правильную позицию. Затем на проходе 2 второй по высоте элемент помещается на свое место. Следовательно, чтобы вычислить сложность, мы должны вычислить сравнения, сделанные алгоритмом~

Использование базовой дискретной математики~

f(n)= (n-1)+(n-2)+(n-3)+.....+ 3 + 2 + 1

f(n)= n(n-1)/2

f (n) = n ^ 2 + O (n) ~ (константы игнорируются для получения сложностей)

f(n)= O(n^2)

Поэтому сложность пузырьковой сортировки составляет O(n^2). Это означает, что время, необходимое для выполнения пузырьковой сортировки, пропорционально n^2, где n — общее количество элементов в массиве.