algorithm - 下限 : 入力サイズ n のクラスのアルゴリズムが必要とするリソース

Question

次の下限を見つけるように求められました。

T(n)= 23n^3-n^2-n.

だからここに私がどのように進んだかがあり、適切な方法で取り組んでいるかどうかはわかりません:

T(n)>=c(23n^2-n^2) すべての n が n>=n0 より大きい場合

すべての n>=2 に対して 23n^3-n^2-n >=(22n^2)。

T(n)>=c|n^2| すべての n>=2 に対して c=22 n0=22。T(n) はビッグ オメガ n^2

助けてください！

Answer 1

に注意しn^3 >= n^2てくださいn >= 1。だから、-n^3 <= -n^2のためにn >= 1。

に注意しn^3 >= nてくださいn >= 1。だから、-n^2 <= -nのためにn >= 1。

そう

23n^3 - n^2 - n >= 23n^3 - n^3 - n^3 = 21n^3.

したがって、21n^3は適切な下限です。

直感的には、これは本質的に明らかに立方体であるため意味があり、したがって、一部23n^3 - n^2 - nの下限と上限が必要です (下限と上限は異なります)。cn^3ccc