Большой О нотации

Question

Просто нужно подтверждение на что-то очень быстрое.Если для выполнения алгоритма требуется n(n-1)/2 тестов, будет ли большой ой O(n^2)?

Answer 1

n (n-1) / 2 расширяется до (n^2 -n) / 2, то есть (n^2/2) - (n/2)

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

С n^2/2 вы можете безопасно удалить часть / 2 в асимптотическом анализе записи.

Это упрощает до n^2

Поэтому да, это в O (n ^ 2)

Answer 2

Да, это правильно.

n(n-1)/2 расширяется до n^2/2 - n/2:

Линейный член n/2 выпадает из-за более низкого порядка.Это оставляет n^2/2.Константа поглощается в Big-O, оставляя n^2.

Answer 3

Да:

n(n-1)/2 = (n2-n)/2 = O(n^2)

Answer 4

Да, это так.n(n-1)/2 равно (n^2 - n)/2, что явно меньше, чем c*n^2 для всех n>=1, если вы выберете c, то есть как минимум 1.