T（n）= n/xは$ n $で線形ですか？

私は線形時間アルゴリズムがo（n）で表されることを知っています。

T（n）= n/xは、正の数xに対して$ n $で線形ですか？

つまり、n/x = o（n）ですか？

出典

2017-10-08 mallea

xの値に依存しますが、xがnに近い場合はo（1）になります。 –

@Atul Kumarここでは漸近的な行動について話しています。 xは定数なので、nが無限大に近づくにつれて "nに近い"ことはできません。 – jspurim

漸近的な振る舞いでは、定数は非常に大きくすべきではないので、定数を調べる必要があります。 @jspurim –

号

T(n) = n/xT(n) = xnが線形であると同様に、線形です。あなたの関数がちょうどnに何らかの定数cを乗じたものなら、それは線形です。この特定の場合、c=1/x。

formal definition of small oを使用して確認することもできます。正式

、F（N）O（G（n）を）= Nとして→∞は、そのような定数Nが存在毎に正の定数εことを意味| F（n）が| < =ε| g（n）|この場合、すべてのn> = N.

ため、ε=1/2xを選ぶと、あなたはNがn/x = o(n)を作るための条件を満足するために見つけることができるように文句を言いません。

直感的に言えば、f(n)がg(n)によって支配されている場合は、最終的には非常に小さな定数で「遅くg（n）ダウン」したとしても1つしかありません。

出典

2017-10-10 16:08:54 jspurim

定数cを有理数にすることはできますか？ – mallea

はい、cには任意の実数を使用できます。あなたの関数が実行時間を表すと仮定すると、負の値cは意味をなさないが、正の実数は有効です。具体的な例：並べ替えられた値の配列 'A 'と値' x'が与えられた場合、 'x'が[median]（https://en.wikipedia.org/wiki）/Median）を返します。これは、配列Aの半分を横切ることで解けるので、 'A 'に' n'要素がある場合、 'T（n）= n/2'でこれを解くことができます。このアルゴリズムはまだ線形です。もしあなたが 'A'のサイズを2倍にすれば、問題を解決するのに2倍の時間がかかります。 – jspurim

'T（n）= log（n）'時間にバイナリ検索を使って同じ問題を解決することができます。これは実際の線形解法（ 'A'の2倍の大きさです。長いです）。 – jspurim

T（n）= n/xは$ n $で線形ですか？

答えて

関連する問題