0

基本的なランタイムの理解に問題があります。誰かが明確にしてくれるかもしれません。この関数の実行時間を決定するにはどうすればよいですか?

f = O(g)どちらかというと判断する必要がありf = omega(g)ますf = theta(g)

f(n) = 100n + logn
g(n) = n + (logn) 2

100nとnは同じ順序です。この時点で線形time > log time;であり、ログ部分を確認する必要がありますか? または、それを判断できf = theta(g)ますか？

4

1 に答える 1

1

それらが同じ桁数であることを安全に判断できます。「ログ部分」を見る必要はありません。

これは、この特定のケースの正式な証明です。一般的な証明は、極限演算から示すことができます。

h(n) = f(n)/g(n)n が無限大に近づくときの関数を見てみましょう。関数が 0 より上で、m既知の数値より下に制限されている場合f(x) = Theta(g(x))(Theta がどのように定義されているかによります)。

だから私たちは持っていますh(n) = (100n + logn)/(n + logn^2)

任意の実数 x について示せば、自然数にも当てはまることがわかります。したがって、次のことを示すだけで十分です。

h(x) = (100x + logx)/(x + logx^2)

ロスピタルの法則により、分子と分母の導関数が存在し、元の​​関数の極限よりも収束する場合、元の関数の極限が存在し、同じ数に等しいことがわかります。それを適用して取得しましょう：

lim x-> infinity , h(x) = (100x + logx)/(x + logx^2) = 

lim x-> infinity , (100+1/x) / (1 + (2log(x) / x) )

x が無限に近づくと 1/x が 0 に近づき、x が無限に近づくと (2logx)/x が 0 に近づくことがわかっています (つまり、(時間 > ログ時間))。したがって、極限演算から得られます

リム x-> 無限大 h(x) = 100/1 = 100

極限は R に存在し、非ゼロであるため、表示したい f(x) = Theta(g(x)) が得られます。

于 2013-05-18T16:20:42.430 に答える