私は大規模なデータ セットを使用するアルゴリズムのコースでこの課題を抱えてここに座っています。Big-Oh には完全に自信がありますが、Little-Oh 表記法を使用すると混乱してしまいます。
私は課題の解決策を望んでいないので、提示しません。代わりに、私の質問は、時間の複雑さo(log n)をどのように解釈するかです。
定義から、アルゴリズム A は o(log n) よりも漸近的に遅く成長しなければならないことはわかっていますが、これがアルゴリズムが一定時間で実行されなければならないことを意味するのか、それとも log n であってもよいのかはわかりませんc = 1 のような特定の条件下、または実際にlog (n-1)である場合。
アルゴリズムの実行時間がO(log n)であるとしますが、実際には 2 回の反復を行い、そのため c = 2 ですが、2*log nは依然としてO(log n)です。これが成り立たないと言うのは正しいですか?リトルオー？
どんな助けでも大歓迎です。明確にするために厳密に必要な場合は、課題を提供します
fが 'little-oh-of 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)。
Little-Oh の場合、すべての x について f(x) が g(x) よりも小さい必要はありません。xの特定の値の後でのみ小さくする必要があります。（あなたの質問については、特定の条件下では引き続きログ n にすることが許可されています。）
例えば：
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) よりも大きくなります。しかし、これはリトルオーが関心を持っていることではなく、変化の速度がすべてです。