math - アルゴリズム効率のためのオメガの計算

Question

アルゴリズムの効率の計算が理解できません。これが私の問題の1つです。誰かがこれを理解するためにどの方法が使用されているかを説明できますか? この本は非常に紛らわしく、これに多くの時間を費やしていません。

関数 n^3 と 3n^3 - 2n2 + 2 の間の適切な Ω 関係を見つけ、定数 c と n0 を見つけます。

n^3 と 3n^3 の間に大きな違いはないことはわかっていますが、定数 c と n0 を見つける方法がわかりません。

Answer 1

関数 n ³と 3n ³ - 2n ² + 2 は、実際には互いの Θ であり、同じ速度で成長することを意味します。各関数を他の関数と一緒に下限にできるはずです。

最初の方向では、

3n ³ - 2n ² + 2

≥ 3n ³ - 2n ²

≥ 3n ³ - 2n ³

= n ³

したがって、c = 1 および n ₀ = 0 を選択すると、任意の n ≥ n ₀に対して 3n ³ - 2n ² + 2 ≥ cn ³が得られるため、3n ³ - 2n ² + 2 = Ω(n ³ )

逆方向については、ことわざの演習として読者にお任せします。:-)

お役に立てれば！