1

私は現在、まだあまり経験したことのないトピックである Big-O を取り入れたクラスを受講しています。以下は、私が答える必要がある質問のタイプの例です。注: これらの質問は、宿題でする必要がある質問と似ていますが、数字などが変更されています。

私は解決策を探していません。効果的に証明を書く方法についての説明を探しています。

問題は次のようになります (最初の式は f(n)、2 番目の式は g(n)):

(a) 5^(log_5(n)) and 3n+2
(b) n^2 and sqrt(3)^(log(n))

証明を効果的に書くためには、

|f(x)| <= c|g(x)| for all x >= k

(k == n_0 は、どのように教えられたかによって異なります) したがって、最初の質問については、質問を単純化して次のようにします。

n is O(3n+2)

そして、2番目のものを開始する方法が完全にはわかりません。

ここから、値 c と k をどのように選択しますか? それらは単に方程式を真にする任意の値ですか、それとも私が見逃しているものがありますか? 多くの例を見てきましたが、c と k の値を取得する方法を説明しているものはありません。

ご協力いただきありがとうございます！

4

1 に答える 1

0

とにかくbig-Oの目的が何であるかを覚えておいてください。あなたは、関数が他の特定の関数（その上限）よりも「速く」ない速度で、十分な大きさの入力で成長することを示しようとしています。そのことを念頭に置いて、kはかなり任意ですが、不等式が成り立つkの最小の非負の値を選択することをお勧めします。明確な最小のkが見つからない場合は、機能するものを選択してください。また、通常、上限の最上位項で定数を「破棄」するため、同様に、不等式が成立する最小の正のcを選択します。繰り返しますが、「最小」を決定できない場合は、機能するものを選択してください。kとcを思い出したら代表する、これが彼らをどうするかということを覚えるのはそれほど難しいことではありません。

あなたの先生/教授は異なる考えを持っているかもしれないので、あなたはおそらく再確認したいと思うでしょう、しかしこれはこの特定の音楽専攻の人がアルゴリズムのクラスから覚えていることとほとんど同じです。

お役に立てば幸いです。

于 2011-01-21T23:23:16.080 に答える