Нет формулы как таковой. Вы можете найти формальное определение здесь:
f(n) = O(g(n)) means there are positive constants c and k, such that 0 ≤ f(n) ≤ cg(n) for all n ≥ k. The values of c and k must be fixed for the function f and must not depend on n. ( обозначение big-O ).
Что я понял из твоего вопроса, так это то, что ты не понимаешь сути нотации big-O. Если ваша сложность составляет, например, O(n^2), то вы можете гарантировать, что существует некоторое значение n (больше k), после которого f(n) ни в коем случае не будет превышать c g(n).
Давайте попробуемf(n) = 2n + 2:
- . Как видно из самой функции, вы не можете установить значение
c равным 2, так как вы хотите найти f(n) ≤ c g(n). Если вы подключите c = 2, вы должны найти k такой, что f(n) ≤ c g(n) для n ≥ k. Понятно, что нет n, для которого 2n ≥ 2n + 2. Итак, мы переходим к c = 3. Теперь давайте найдем значение k. Итак, решаем уравнение 3n ≥ 2n + 2. Решение:
3n ≥ 2n + 2
=> 3n - 2n ≥ 2
=> n ≥ 2
Поэтому для c = 3 мы нашли значение k = 2 (n ≥ k).
Вы также должны понимать, что ваша функция не просто O(n). Это также O(n^2), O(n^3), O(n^4) и так далее. Все потому что соответствующие значения c и k существуют для g(n) = n^2, g(n) = n^3 и g(n) = n^4.
Надеюсь, это поможет.