どのように計算することができますか

Question

私のアルゴリズムは常にn!*4^nのステップを実行することがわかりました。私は、その複雑さがO(n!*4^n)になるか、それが別のものになるのかを知りたいですか？ありがとう。

Answer 1

正確にはn!*4^nのステップでは、大きなoh表記の必要はありません。

はい、それはO(n!*4^n)の複雑さを持っていることを意味します。

Answer 2

あなたのアルゴリズムが常にn!⋅4ⁿの手順を実行することを確信している場合、それはO(n!⋅4ⁿ)だだけでなく、それはΘ(n!⋅4ⁿ)だだけでなく、それはΩ(n!⋅4ⁿ)です。

Answer 3

それはΘ(n!⋅4ⁿ)だとΘがOの下限であるので、それはまたΩ(n!⋅4ⁿ)だもO(n!⋅4ⁿ)です。

あなたのステップで何をしているのですか？各ステップがO（1）の場合、この表記は成立しますが、それ以外の場合は手順に依存します。

なぜそれがO(n!)とは言えないのですか？あなたは一定で見つけることができないためcように：理由は任意の定数cとき4ⁿ > c（のために例えば

N⋅4ⁿ≤c⋅n！nの> nは0

_{！上記の不等式の上の方が間違っています。}