O((n^3)/4) не имеет смысла с точки зрения обозначения big-O, поскольку оно предназначено для измерения сложности как отношения аргумента. Деление на 4 не влияет, так как это меняет значение отношения, но не его природу.
Все они эквивалентны:
O(n^3)
O(n^3/4)
O(n^3*1e6)
Другие термины имеют смысл только тогда, когда они включают n термин, такой как:
O(n^3 / log(n))
O(n^3 * 10^n)
Как справедливо указывает Энтони Канаго, принято:
- сохраняет только срок с наивысшей скоростью роста для сумм:
O(n^2+n) = O(n^2).
- избавиться от констант для продуктов:
O(n^2/4) = O(n^2).
Кроме того, я не всегда согласен с этим первым правилом во всех случаях. Это хорошее правило для определения максимальной скорости роста функции, но для таких вещей, как сравнение алгоритмов (a) , где вы можете разумно установить ограничение для входного параметра, что-то вроде O(n^4+n^3+n^2+n) заметно хуже, чем просто O(n^4).
В этом случае любой член , который зависит от входного параметра, должен быть включен. На самом деле, даже постоянные термины могут быть полезны там. Сравните, например, O(n+1e100) с O(n^2) - последний будет превосходить первый в течение некоторого времени, пока n не станет достаточно большим, чтобы влиять на постоянный член.
(a) Есть, конечно, те, кто сказал бы, что его не следует использовать таким образом, но прагматизм часто побеждает догматизм в реальном мире: -)