教科書のparticalur Big-Oの例を理解できません

Question

これまでBig-O表記を理解しており、計算方法がわかりました...ほとんどの状況は分かりやすいです。しかし、私はこの1つの問題に遭遇しましたが、私の人生のためには理解できません。

説明：式に最適なbig-O表記を選択します。

(n^2 + lg(n))(n-1)/(n + n^2) 

答えはO（n）です。それはすべて罰金とダンディーですが、分子のn^3因子を考えれば、それはどのように合理化されていますか？ n^3は最高ではありませんが、f(n) <= O(g(n))の間に「最小」の基準があると思いましたか？

本書では数学的な内部的な働きは説明されていませんが、すべてが可能な解決策に注入されています（f(n)をとり、f(n)よりわずかに大きいg(n)を生成しています）。

こんにちは。あなたがしなければならない場合は、数学、または数学の参照に夢中になります。

また、1つのコードでは、1行あたりの時間単位はどのように決定されますか？ 1行のコード（または複数行のコード）に基づいて対数時間を決定するにはどうすればよいですか？変数を宣言して設定することは1単位時間と考えられますが、状況が悪くなると、どのように解決策にアプローチするのでしょうか？非厳格な答え

Answer 1

：

1. は、分子製品の配布は、我々は分子がn^3 + n log(n) - n^2 - log nであることがわかります。
2. 大きな分子の分子はnの場合にはn^3と大きくなり、分母は大きい場合にはn^2のように大きくなります。nです。
3. 我々は、成長が大きいとn、またはO(n)の場合、n^{3 - 2}と解釈します。あなたがウルフラムアルファにこのアルゴリズムを投げる場合

Answer 2

、you get this generic result：

あなたが拡大した場合（FOIL）それは、あなたが（およそ）二次関数で割った立方体の機能を取得します。ビッグ-Oでは、定数は問題と、より大きなパワー勝あなたがsomething like thisになると思いません：ここから

残りは数学的帰納です。全体的なアルゴリズムは、nの値が大きくなるにつれて直線的に増加する。 かなりではないので、（n）のBig-Omegaはあるとは言えませんが、償却された一定の成長率のため、O（n）にかなり合理的に近いです。

また、「Big-Oルールに基づいているので、分母からnの因子を落とすことができ、簡単な除算でO（n）を得ることができます」と言います。しかし、これがまだではないと思うのは、私の考えでは重要です。 linearです。

マインドでは、これはクラスにとって満足できるレベルよりも厳密ではない説明ですが、これは実行時に数学ベースの視点を提供します。