4

完全な開示：これは宿題の問題です。私は正直なところ、それがとても単純に見えるとき、それが長い間私を回避してきたことを少しおかしく思っています。

さて、質問は、f（n）= n ^ 2 * log（n）、g（n）= n^2.1です。fはtheta（g）に含まれていますか？

特定のn0 、f（n）<= c 1 g（n）<= c 2 f（n）を超えるように、定数c 1、c2を考え出す必要があります。しかし、fがtheta（g）にあるかどうかさえわかりません。私はそれが混乱しています。

4

2 に答える 2

1

私が覚えていることから、f(n) が theta(g(n)) にあることを証明するには、2 つの異なるアプローチを取ることができます。

  1. f が O(g) にあることを証明し、g が O(f) にあることを証明してください。

  2. f が O(g) にあることを証明し、f が BigOmega(g) にあることを証明してください。

于 2010-11-08T01:02:19.047 に答える
0

最初に文言に注意してください。「fはtheta（g）にあります」。これは、彼らが最初にそれが真実であるかどうかについて知識に基づいた推測をすることを望んでいることを意味します。

反対の質問：theta（n）はtheta（n * log（n））と同じですか？私たちはその答えを知っています...いいえ、そうではありません（そうでなければ、比較ベースのソートは線形になります）。これはあなたの質問に何を示唆していますか？

主張を証明するために、MahlerFiveによる他の答えに従ってください。完全を期すために、主張を反証しようとするために、敵が定数c1とc2を思いついたと仮定します。ここでの目標は、敵がどのような定数を使用していても（つまり、すべてのc1とc2に対して）、境界を満たすn0がないことを示すことです。つまり、c1とc2を選択する方法がないことを示します。あなたの場合のトリックは、おそらくf関数のlog（n）係数に集中しています。log（n）は単調に増加しており、より大きなn値をプラグインすることで、その係数を任意に大きくできることを示しています。

これで、問題を自分で解決することに満足しながら、少しでもうまくいくことを願っています。私が完全に間違っている場合は、他の読者が私を訂正すると確信しています。

于 2010-11-08T01:19:06.457 に答える