アルゴリズムの実行時の複雑さを理解できます。しかし、アルゴリズムの実行時の複雑さがO（n）であることを知ったとき、少し混乱します。
f（n）<g（n）であることがわかります。
g（n）とは正確には何ですか..？
ルーキーの質問でごめんなさい。
ありがとう。
2 に答える
1
実数のサブセットで定義された2つの関数としますf(x)。g(x)1つの書き込み
f(x) = O(g(x)) as x -> infinity
M正の実数と次のx0ような実数が存在する場合にのみ
|f(x)| <= M |g(x)| for all x > x0
一般に、f(x)は、の入力スケールでのアルゴリズムの実際のコスト（実行ステップ数など）ですがx、の複雑さの動作を特徴付けるために使用できるg(x)よりもはるかに単純です。f(x)f(x)
于 2012-11-20T02:27:33.053 に答える
0
f（x）とg（x）は単なる関数のペアであるというコメントに同意します。f（x）= O（g（x））は、それらが特定の方法で関連していることを示します。
これがよく使用される方法は、f（x）を複雑で、特徴付けが難しい機能にすることです。g（x）ははるかに単純な関数です。f（x）= O（g（x））を知ることで、xが増加するにつれてf（x）の限界を感じることができます。
コンピュータサイエンスへの応用は、f（x）を入力サイズxの関数としてのプログラムの振る舞いの尺度にすることです。たとえば、f（x）は、x要素配列をソートする際の比較の最大数、または一部のアルゴリズムで使用されるメモリのワード数である可能性があります。f（x）はしばしばかなり乱雑になります。
f（x）= O（g（x））を証明できるように、すてきでクリーンな関数g（x）を見つけることで、物事を簡単にすることができます。
たとえば、一部のアルゴリズムは、サイズ30未満の入力の場合、入力の35操作または要素あたり10操作の大きい方、またはすべての大きい入力の場合、要素あたり1000操作を実際に取る場合があります。
f（x）= O（x）であることに気付くと、アルゴリズムの比較がはるかに簡単になり、簡単になります。
これは、f（x）<g（x）と言うことと同じではないことに注意してください。私の例では、xが大きい場合、f（x）はg（x）の1000倍になります。これは、g（x）が、xが大きくなるにつれてf（x）がどのように動作するかをキャプチャすることを意味します。
于 2012-11-20T02:25:12.927 に答える