同じ式が異なるbig-O値を返すのはなぜですか？

Question

講義スライドに示されている例では、big-o解析が私を混乱させます。

それは述べている：2N^2 + 4Nは= O（N^2）と2N^2 + 4N = O（N^4）

誰かが同じ式が異なる結果を生成することができますどのように説明できますか？ありがとう

Answer 1

まず第一に"="は、 "等しい"という意味ではなく、アルゴリズムの分析の意味で "あり"を意味します。 big-Oのポイントは、これを満たすことです。

f(x)がの場合、cが正の数です。

あなたのケースでは、2n^2 + 4n = O(n^2) AND 2n^2 + 4n = O(n^4)が該当します。しかし、我々はアルゴリズムを記述するためにここで常に「最良の関数」を使用するので、O(n^2)を使用します。

f(x)は、Ω(h(x)) iff 0<=c*h(x)<=|f(x)|です。さて、あなたはh(x)=g(x)を持っている場合、それはf(x)を意味[「ビッグO」表記の平易な英語の説明とは？]のΘ(g(x))