Big O обозначение константы

Question

Я рассчитываю, что моя сложность выполнения будет , что такое Big O обозначение этого?

Например, если моя сложность выполнения является 4 + п то его Big O = О (п).

Answer 1

Давайте посмотрим свободно в определении того, что мы подразумеваем под f(n) is in O(g(n)):

f(n) в O(g(n)) означает, что c · g(n) является верхней границей на f(n). Таким образом, существует , существует константа c, так что f(n) ≤ c · g(n) для имеет достаточно большое значение n (т. Е. n ≥ n0 для некоторой константы n0).

Вы можете рассматривать постоянную функцию так же, как любую другую функцию, w.r.t. анализируя его асимптотическое поведение с использованием, например, большой-O-обозначение.

f(n) = 4 
g(n) = 1 

f(n) ≤ c · g(n) = c · 1, for c ≥ 4 and for all n   (*) 

    (*) with e.g. n0=0 and c=4 => f(n) is in O(1) 

---

Примечание: в качестве Ctx отмечает в комментариях ниже, O(1) (или, например, O(n)) описывает набор функций, так, чтобы быть полностью правильным, f должны быть описаны как в O(1) (f ∈ O(n) , f: s установить членство в O(1)), а не "f(n) находящийся в O(1)". Однако вы, вероятно, можете ожидать, что менее строгая версия «f(n) находится в O(1)» (или около O(g(n))) так же часто в Интернете, по крайней мере за пределами научных статей.