リトルオーの詳細な記譜、CSの宿題、実際の課題を除く

Question

私は大規模なデータセットを扱うアルゴリズムに関するコースでこの課題を抱えてここに座っていますが、Big-Oh については完全に自信を持っていますが、Little-Oh 記法の使用により混乱してしまいました。

私は課題の解決策を望んでいないので、それを提示しません。代わりに私の質問は、時間計算量をどのように解釈するかです o(ログn)?

定義から、アルゴリズム A は o(log n) よりも漸近的に遅く成長する必要があることはわかっていますが、これがアルゴリズムを一定時間で実行する必要があることを意味するのか、それともまだ一定時間で実行できるのかどうかはわかりません。 ログn c = 1 などの特定の条件下、または実際に c = 1 であるかどうか ログ (n-1).

アルゴリズムの実行時間が O(log n) しかし、実際には 2 回の反復を行うため、 c = 2 になりますが、 2*ログn まだです O(log n), 、これはリトルオーには当てはまらないと言ったのは正しいでしょうか？

ご協力をよろしくお願いいたします。厳密に説明が必要な場合は、課題を提供します。

Answer 1

言うには f は「リトル・オー・オブ・G」です f = o(g), という商を意味します。

|f(x)/g(x)|

として0に近づきます x 無限に近づく。あなたの例を参照すると、 o(log n), 、そのクラスには次のような関数が含まれています log x / log (log x), sqrt(log x) などなど、 o(log x) 絶対に意味するものではありません O(1). 。一方で、 log (x/2) = log x - log 2, 、 それで

log (x/2) / log x = 1 - log 2 / log x -> 1

そして log (x/2) クラスにいません o(log x).

Answer 2

Little-Oh の場合、すべての x について f(x) が g(x) より小さい必要はありません。x の特定の値を超えた後にのみ小さくなる必要があります。(ご質問の件ですが、一定の条件下では引き続きログインが許可されています。)

例えば：

 let f(x) = 5000x and g(x) = x^2

x が無限大に近づくときの f(x) / g(x) は 0 になるため、f(x) は g(x) の完全な値になります。ただし、x = 1 では、f(x) は g(x) より大きくなります。x が 5000 より大きくなって初めて、g(x) が f(x) より大きくなります。

little-o が実際に教えてくれるのは、g(x) は常に f(x) よりも速い速度で増加するということです。たとえば、x = 1 と x = 2 の間で f(x) がどれだけ増加したかを確認します。

 f(1) = 5000
 f(2) = 10000 - f(x) became twice as big

次に、同じ間隔で g(x) を見てみましょう。

 g(1) = 1
 g(2) = 4 - g(x) became four times bigger

x の値が大きくなると、この割合はさらに増加し​​ます。ここで、g(x) はより速い速度で増加し、x を無限大に拡張するため、ある時点で f(x) より大きくなります。しかし、little-o が懸念しているのはこれではなく、すべては変化率に関するものです。