問題タブ [little-o]

オンラインで検索した限り、計算に時間がかかるために実際には解決できないアルゴリズムの例を見つけることができません。

アルファ ケンタウリへの旅でロケット船の近くを通過する各星の数、サイズ、位置を数えることなどの例を考えようとしていました。これは良い例でしょうか？つまり、星系は 26 兆マイル近く離れています。

編集: 私は Big-O と Little-O 表記法に関する短いプレゼンテーションを行っており、問題の解決策が実際には解決可能である理由について、通常とは異なることを考えたかったのですが、原理的には解決できない可能性があります。計算に非常に長い時間がかかるため、Big-O を使用して見積もりを作成する理由です。星を選びたかったのは、他の科目よりも面白そうだからです。

ありがとう！

関数 f: R -> R が f(x) = mx + c として定義され、R 内のいくつかの m、c > 0、および x であるとします。f(x) は o(x) に属しますか?

答えが「いいえ」の場合、o(x) には部分線形関数のセットが適切に含まれていないと結論付けることができますか?

私がこれを尋ねている理由: f(x1) + f(x2) = mx1 + c + mx2 + c > m(x1+x2) + c = f(x1+x2)。しかし lim x-> infinity f(x)/x = 2. この意味で f(x) は o(x) にはありません。ただし、o(x) は一連の準線形関数を表します。それが私の混乱の元です。

f(n),g(n)のような2 つの機能がありf(n)=o(g(n))ます。

明確にするために、私は少しoを取っています

私に与えられたその情報で、それは可能ですf(n)=Omega(g(n))。

Little-oの定義が私に言っているので、私にはそれは不可能に思えます

ありがとう！