Big-O Proofを正しく解決する

Question

私はまだBig-Oで多大な経験をしていないトピックを取り入れています。ここで私が答える必要のある質問のタイプの例を示します。ご注意：これらの質問は宿題のために必要なものと似ていますが、数字などは変更されています。

私はないがソリューションを探しています。私は効果的に証拠を書く方法についての説明を探しています。

問題は次のようになり（最初の方程式をf（n）の第二は、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） だから最初の1のために、私は

n is O(3n+2) 

への質問を簡素化

と私は2番目の方法を始める方法は完全にはわかりません。

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

ありがとうございました！

Answer 1

big-Oの目的はとにかくあることを覚えています。十分な大きさの入力で、ある特定の他の関数（その上限）よりも速い速度で関数が大きくなることを示しています。そのことを念頭に置いて、kはかなり恣意的ですが、不等式が成立する最小の負でない値のkを選択することをお勧めします。最小のkが見つからない場合は、動作するものを選択してください。また、上界の最も重要な項に定数を「投げ捨てる」ため、同様に、不等式が成立する最も小さな正のcを選択します。もう一度、「最小」を判断できない場合は、動作するものだけを選択してください。 kとcが何であるかを思い出したら、これが何であるかを覚えておくのはそれほど難しいことではありません。

あなたの教師/教授は考え方が異なるかもしれませんので、おそらく二重チェックしたいと思うかもしれませんが、これは音楽専門家がアルゴリズムから覚えているものですクラス。

希望に役立ちます！