При сравнении времени выполнения как определить, какие значения следует отбросить

Например.
O (n (n+1))
Это просто упростит до n^2
Потому что n^2+n вы бы отбросили n

Также
2000n^2
Было бы просто n^2

Также
0.001 n^3 будет просто n^3

Правильно ли это?

1 ответ

  1. O(n(n+1)) упроститO(n^2), поскольку n(n+1)меньше или равен постоянному коэффициентуn^2, для достаточно больших n:

    n(n + 1) <= n^2 + n <= n^2 + n^2 <= 2n^2

    Другие упрощения являются правильными, потому что вы просто удаляете постоянный фактор.

    В принципе, можно удалить из выражения постоянный фактор и любые медленно растущие термины.