Как я могу вычислить сложность

Question

Я обнаружил, что мой алгоритм всегда будет делать n!*4^n шагов.Я хотел бы знать, будет ли его сложность O(n!*4^n) или что-то еще?Спасибо.

Answer 1

Это Θ(n!⋅4ⁿ) и потому что Θ является нижней границей для O, это также O(n!⋅4ⁿ) Также это Ω(n!⋅4ⁿ).

Просто важно то, что вы делаете в своих шагах?Если каждый шаг равен O (1), это обозначение выполняется, но в других случаях это зависит от ваших шагов, я предлагаю показать нам вашу функцию, чтобы увидеть, что шаги.

И почему вы не можете сказать, что этоO(n!)?потому что вы не можете найти постоянную c такую, что:

n! ⋅4ⁿ ≤ c⋅n !, для n> n ₀

потому что для любой константы c, когда 4ⁿ > c (например, когда n ≥ c) выше неравенства, неверно.

Answer 2

Если вы уверены, что ваш алгоритм будет выполнять всегда n!⋅4ⁿ шагов, это будет O(n!⋅4ⁿ), а также Θ(n!⋅4ⁿ) и Ω(n!⋅4ⁿ).

Answer 3

Если он делает точно n!*4^n шагов, то нет нужды в больших ой записи.

И да, это означает, что он имеет O(n!*4^n) сложность.